LeetCode Longest Substring Without Repeating Characters

Problem statement

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

Problem statement taken from: https://leetcode.com/problems/longest-substring-without-repeating-characters

Example 1:

Input: s = 'abcabcbb'
Output: 3
Explanation: The answer is 'abc', with the length of 3.

Example 2:

Input: s = 'bbbbb'
Output: 1

Example 3:

Input: s = 'pwwkew'
Output: 3

Example 4:

Input: s = ''
Output: 0

Constraints:

- s consists of English letters, digits, symbols and spaces.
- 0 <= s.length <= 5 * 10^4

Explanation

Brute force

A brute force solution will be to iterate through all possible substrings of the input string. Let's say we have a function checkUniqueString which returns true or false based on a string that has all unique characters or not.

We generate all possible substrings using two nested for loops and inside which we call checkUniqueString function.

A small code block in C++ will look like this.

int n = s.length();

for (int i = 0; i < n; i++){
    for (int j = i; j < n; j++){
        if (checkUniqueString(s, i, j)){
            // logic for updating the max length substring
        }
    }
}

checkUniqueString will iterate over the string once to check for any repeating character. Hence it will take O(N) time.

The above two nested for loops will take O(N²) time. The total time complexity is O(N3).

Sliding Window

The sliding window approach is widely used in many arrays and string problems. The above brute force approach can be optimized using a sliding window.

A sliding window is a range of elements in the array/string that is defined by start and end indices, i.e., [i, j) (left index included, right index excluded). The window can be used to slide its range in a certain direction. So if we right shift the window to right by 1 element then [i, j) will change to [i + 1, j + 1).

Algorithm

Initially, the window size is 0 as we have pointed left and right at the first index. We keep on incrementing right till we find a repeated character in the string. When right finds a repeated character, we found the maximum size of substrings without duplicate characters starting at index left.

We keeping doing for all elements of the string till we reach the end.

- Initialize variables left, right, and ans to 0.
- Create an array named as chars of length 128.
  This will store the number of times an element appeared in an array.
- Loop while ( right < s.length() )
  - set char r = s[right]
  - increment chars[r]++
  - Loop while ( chars[r] > 1 )
    - set char l = s[left]
    - decrement chars[l]--
    - increment left++
  - set maximum till now in ans.
    ans = max(ans, right - left + 1)
  - increment right++
- return ans

The time complexity of the above solution is O(N).

Optimized sliding window

The above solution can be optimized further. Instead of iterating over each index of the string, we define a mapping of the characters to its index. Then we skip all the characters immediately when we find a repeated character.

C++ solution

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        unordered_map<char, int> map;

        for(int i = 0, j = 0; j < s.size(); j++){
            if(map.find(s[j]) != map.end()){
                i = max(map[s[j]], i);
            }
            ans = max(ans, j - i + 1);
            map[s[j]] = j + 1;
        }

        return ans;
    }
};

Golang solution

func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]int)
    i, ans := 0, 0

    for j := 0; j < len(s); j++ {
        if v, ok := m[s[j]]; ok {
            if v > i {
                i = v
            }
        }

        if j - i + 1 > ans {
            ans = j - i + 1
        }
        m[s[j]] = j + 1
    }

    return ans
}

Javascript solution

var lengthOfLongestSubstring = function(s) {
    var mapping = {};
    var i = 0;
    var ans = 0;

    for(var j = 0; j < s.length; j++){
        if(mapping[s[j]]) {
            if(mapping[s[j]] > i) {
                i = mapping[s[j]];
            }
        }

        if(j - i + 1 > ans){
            ans = j - i + 1;
        }
        mapping[s[j]] = j + 1;
    }

    return ans;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

s = 'abcdeafb'
m = map()
ans = 0

Step 1: i = 0, j = 0
        s[j] = 'a'
        m['a'] = j + 1 = 1
        ans = max(ans, j - i + 1) = max(0, 0 - 0 + 1) = 1

Step 2: i = 0, j = 1
        s[j] = 'b'
        m['b'] = j + 1 = 2
        ans = max(ans, j - i + 1) = max(1, 1 - 0 + 1) = 2

Step 3: i = 0, j = 2
        s[j] = 'c'
        m['c'] = j + 1 = 3
        ans = max(ans, j - i + 1) = max(2, 2 - 0 + 1) = 3

Step 4: i = 0, j = 3
        s[j] = 'd'
        m['d'] = j + 1 = 4
        ans = max(ans, j - i + 1) = max(3, 3 - 0 + 1) = 4

Step 5: i = 0, j = 4
        s[j] = 'e'
        m['e'] = j + 1 = 5
        ans = max(ans, j - i + 1) = max(4, 4 - 0 + 1) = 5

Step 6: i = 0, j = 5
        s[j] = 'a'
        m['a'] is 1
        set i = max(i, m['a']) = max(0, 1) = 1
        ans = max(ans, j - i + 1) = max(5, 5 - 1 + 1) = 5
        m['a'] = 6

Step 7: i = 1, j = 6
        s[j] = 'f'
        m['f'] = j + 1 = 7
        ans = max(ans, j - i + 1) = max(5, 6 - 1 + 1) = 6

Step 8: i = 1, j = 7
        s[j] = 'b'
        m['b'] is 2
        set i = max(i, m['a']) = max(1, 2) = 2
        ans = max(ans, j - i + 1) = max(6, 7 - 2 + 1) = 6

So the answer is 6.