Problem Statement

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

Test Cases

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.

Intuition

We have to consider all the substring and see in each substring whether we see any repeating character. If not, then we need to track down the length and find out the maximum. But this would cause N^2 complexity if we go with 2 loops approach.
Instead, we can just have an hashmap to store the indexes so that we would know whether a particular character is seen or not. If its seen and if its within our window, then we can't consider that substring. We need to move the pointer to the next index of the repeating character. In simple way

if hash[char] != -1 && hash[char] >= leftPointer :
    then its in our window, update leftPointer = hash[char] + 1 and 
    hash[char] = rightPointer
else :
    then its not in our window, just update the hash and try to see if it contributes to a larger length

Approach

• Create an hash array of size 256 as there can be small letters, capital letters, space, numbers etc.
• Maintain 2 pointers, maxLength
• Loop through the string and check if the current char is seen. If not, check for the maxLength and the hash with the char index.

• If already seen, then we have 2 conditions to check.
  ** Is it within our boundary, if yes move left pointer to hash[char] + 1
  ** Else, check the maxLength and update hash[char] = rightPointer.

• Finally return the maxLength.

Complexity

• Time complexity:

  O(lengthOfString)

• Space complexity:

  O(256)

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        int length = s.length();
        int [] storeIndex = new int [256];
        Arrays.fill(storeIndex, -1);
        int maxLength = 0;
        int left = 0;
        int right = 0;
        while (right < length) {
            char currentChar = s.charAt(right);
            // if the char is new
            if (storeIndex[currentChar] == -1) {
                storeIndex[currentChar] = right;
                maxLength = Math.max(maxLength, right - left + 1);
            }
            else {
                // is it beyond our window
                if (storeIndex[currentChar] < left) {
                    storeIndex[currentChar] = right;
                    maxLength = Math.max(maxLength, right - left + 1);
                }
                // or is it within our window
                else {
                    left = storeIndex[currentChar] + 1;
                    storeIndex[currentChar] = right;
                }
            }
            right++;
        }
        return maxLength;
    }
}