Longest Substring without Repeat/ Longest Repeating Substring with Substitution

Longest Substring without Repeat

Given a string s, find the length of the longest substring without repeating characters.

Example

Input: s = “abcabcbb”

Output: 3

Explanation: The answer is “abc”, with the length of 3.

Approach 1:

While there can be a brute-force implementation that inspects all the substring possible for the string s, the algorithm will be an O(N^3) operation, which is too slow.

For this problem, I thought I can have two pointers and use hashmap while iterating through the string to check whether the character is already in the substring or not.

1. First, initialize returning variable ‘result’, two pointers = 0, and a hashmap that stores the characters in the substring.
2. Iterate through the string with one pointer and if the character is not in the hashmap,
3. Set the value to index + 1 since this will be used to update the second pointer’s index if the character is already in the substring.
4. If the character is in the hashmap, update the second pointer’s so that the new substring will start from the index + 1 of the repeated character
5. Update result with each iteration using the two pointers

Implementation:

class Solution:


    def lengthOfLongestSubstring(self, s: str) -> int:
        h = {}
        i = result = 0
        for j in range(len(s)):
            if s[j] in h:
                i = max(i, h[s[j]])
            h[s[j]] = j+1
            result = max(result, j - i + 1)
        return result
        

Complexity Analysis:

Time Complexity: O(N) where n is the length the string s

Space Complexity: O(min(m,n)) where m is the size of the string and the n is the number of unique characters

Longest Repeating Substring with Substitution

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character.

You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example

Input: s = “ABAB”, k = 2

Output: 4

Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.

Approach 1:

1. Initialize two pointers and a result variables, all as integers
2. Make a hashmap that counts for the frequencies of each characters as the pointer “j” iterates through the string
3. Update the hashmap with the pointer “J”
4. Up to the current index, if k changes does not change all the string values to a unionized string of characters that has the current highest frequency, update the second pointer “i” by moving it towards index J
5. Update the result variabales if the conditions above are met

Implementation:

class Solution:


    def characterReplacement(self, s: str, k: int) -> int:
        m = {}
        i,j,result = 0,0,0
        while j < len(s):
            if s[j] not in m:
                m[s[j]] = 1
            else:
                m[s[j]] += 1
            l = j - i + 1
            # if k changes does not change all the string values to the string of character that has the highest frequency
            # update the ith index by discounting the occurrences of other characters
            if l - max(d.values()) > k:
                d[s[i]] -= 1
                if d[s[i]] == 0:
                    del d[s[i]]
                i+= 1
            else:
                result = max(result, l)
            j+=1
            
        return result
      

Complexity Analysis:

Time Complexity : O(N) Space Complexity: O(N) for the hashmap

Reflection

Let’s get in 15 hour work weeks!