Leetcode Amazon Interview Questions

Longest Substring Without Repeating Characters

Leetcode - No. 3

3 Longest Substring Without Repeating Characters

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

1
2
3
4
5
6
7
8
9
10
Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Longest Substring Without Repeating Characters

Problem Analysis

Given a long stringa and We need to find the longest substrg (which have no duplicated character inside the string).

Algorithm Analysis - HashMap

How could I get the value of J? Use the MAP! Since the map has recorded the left recently appears character, so when we meet the same one which is in the map, j will equal to the value of the Max one between j or map.get(character) + 1.

So when we meet the same character, update the left pointer(j)

When we are traversing the string, we need to update two things, and one is the recently appear character in the map and the max Lenght with the substring!

Algorithm - Two Pointers without additional space

Actually, we can use a static array to record the frequencies of each character, so when the right pointer meet a character that stored in the array, use the left pointer to keep moving left and find that repeated character, then move forward one character to avoid duplicated.

Time Complexity Analysis

Time: O(n)

Code Implementation - HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0) return 0;
        int maxLen = Integer.MIN_VALUE;
        
        Map<Character, Integer> map = new HashMap<>();
        
        for(int i = 0, j = 0; i < s.length(); i++) {
            /* Meet the same character */
            if(map.containsKey(s.charAt(i))) {
                /* Update the Left Most index */
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            }
            /* Update the current index of Character */
            map.put(s.charAt(i), i);
            /* Upadte the current max length*/
            maxLen = Math.max(maxLen, i - j + 1);
        }
        
        return maxLen;
    }
}

Code Implementation - Two Pointers without addtional space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
    int left = 0;
    int right = 0;
    int[] freq = new int[256];
    int max = 0;
    
    /* Right pointer keep finding the next possible char */
    while(right < s.length()) {
        char currentCharacter = s.charAt(right);
        /* Meet the not repeated char */
        if(freq[currentCharacter] == 0) {
            /* Update the current max value */
            max = Math.max(right - left + 1, max); 
            freq[currentCharacter]++;
            right++;
        }
        /* Meet the repeated char */
        else {
            /* Used the left pointer to find currentCharacter */
            while(s.charAt(left) != currentCharacter) {
                freq[s.charAt(left)]--;
                left++;
            }
            /* Move forward to let left pointer not pointing to the repeated char */
            freq[s.charAt(left)]--;
            left++;
        }
    }
    return max;
}

Fellow up Question

Longest Substring with At Most Two Distinct Characters

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.

1
2
3
4
5
6
7
8
9
10
Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.
Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s.length() == 0) return 0;
        int leftMost = 0;
        int maxLen = Integer.MIN_VALUE;
        Map<Character, Integer> map = new HashMap<>();
        
        for(int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), i);
            /* If meet the third characters */
            if(map.size() > 2) {
                int indexToRemove = i;
                /* Find the leftMost and remove the farest character out of the map */
                for(int v: map.values()) {
                    indexToRemove = Math.min(indexToRemove, v);
                }
                
                /* Remove the Character from map and Update the LeftMost */
                map.remove(s.charAt(indexToRemove));
                leftMost = indexToRemove + 1;
            }
            
            /* Update the current Max Length */
            maxLen = Math.max(maxLen, i - leftMost + 1);
        }
        return maxLen;
    }
}

FEATURED TAGS
Leetcode Amazon Interview Questions