Leetcode 3. Longest Substring Without Repeating Characters

Screenshot from Leetcode

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⁴
s consists of English letters, digits, symbols and spaces.

Intuition

We have to consider all the substrings and see whether we see any repeating character in each substring. If not, then we need to track down the length and find out the maximum. But this would cause N² complexity if we go with a 2-loop approach.
Instead, we can just have a hashmap to store the indexes so that we would know whether a particular character is seen or not. If it's seen and if it's 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 a 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 a hash array of size 256, as there can be small letters, capital letters, spaces, numbers, etc.
• Maintain 2 pointers, maxLength
• Loop through the string and check if the current character 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 the 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;
    }
}