Longest Substring Without Repeating Characters

---

Longest Substring Without Repeating Characters: Given a string s, find the length of the 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
Explanation: The answer is "b", with the length of 1.

---

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

---

Constraints:

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

---

Try this Problem on your own or check similar problems:

1. Maximum Erasure Value
2. Longest Nice Subarray
3. Optimal Partition of String

Solution:

Java

public int lengthOfLongestSubstring(String s) {
    int maxLength = 0, i = 0, j = 0;
    int[] trackIndex = new int[128];
    Arrays.fill(trackIndex, -1);

    while(j < s.length()){
        char current = s.charAt(j);
        int mapping = (int) current;

        int index = trackIndex[mapping];

        if(index != -1){
            i = Math.max(i, index + 1);
        }

        trackIndex[mapping] = j;
        maxLength = Math.max(maxLength, j - i + 1);
        ++j;
    }

    return maxLength;
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let maxLength = 0;
  let i = 0;
  let j = 0;
  const trackIndex = new Array(128).fill(-1);

  while (j < s.length) {
    const current = s.charAt(j);
    const mapping = current.charCodeAt();

    const index = trackIndex[mapping];

    if (index !== -1) {
      i = Math.max(i, index + 1);
    }

    trackIndex[mapping] = j;
    maxLength = Math.max(maxLength, j - i + 1);
    j++;
  }

  return maxLength;
};

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxLength = 0
        i = 0
        j = 0
        trackIndex = [-1] * 128

        while j < len(s):
            current = s[j]
            mapping = ord(current)

            index = trackIndex[mapping]

            if index != -1:
                i = max(i, index + 1)

            trackIndex[mapping] = j
            maxLength = max(maxLength, j - i + 1)
            j += 1

        return maxLength

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLength = 0;
        int maxFreq = 0;
        int i = 0;
        int j = 0;
        std::vector<int> trackIndex(128, -1);

        while (j < s.length()) {
            char current = s[j];
            int mapping = static_cast<int>(current);

            int index = trackIndex[mapping];

            if (index != -1) {
                i = std::max(i, index + 1);
            }

            trackIndex[mapping] = j;
            maxLength = std::max(maxLength, j - i + 1);
            j++;
        }

        return maxLength;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

Our goal again is to have the longest window fulfilling the problem statement requirements (no repeating characters). We use the same template as we did in Longest Repeating Character Replacement, but this time to correct the invalid window we track the indices of the last occurrence of each character, when we encounter the same character again we have to shrink our window by moving it to the right of the last occurrence of the character (if we haven't already passed this character before i = Math.max(i, index + 1);). We use (int) current to map the character to the 0..127. Useful mapping for other types of problems containing a larger set of different characters:

• int[26] for Letters 'a' - 'z' or 'A' - 'Z'
• int[128] for ASCII
• int[256] for Extended ASCII.