Longest Substring Without Repeating Characters – Java Solution | Python Solution

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" or "bca" or "cab", 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 * 104
• s consists of English letters, digits, symbols and spaces.

Solution:

Step 1:

• Create a Map with Character as Key and Integer (index) as value
• Create variables maxLength and currentLength to store maxLength of substring so far and current substring’s length

Step 2:

• Iterate over string character by character
• start index is set to 0 when starting the loop

Step 3:

• If character is found as key in map, and position found from map value is greater than start meaning it will occur after start point of substring, then update start point to duplicate character’s index + 1 to avoid duplicates in substring.
• Add / update character and it’s latest index to the map

Step 4:

• update currentLength and maxLength accordingly.
  currentLength is derived by
  • currentIndex ( i ) – start + 1
  • if currentLength is greater than maxLength replace.

Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(n)

Java Solution

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        Map < Character, Integer > map = new HashMap < Character, Integer > ();
        int maxLength = 0;
        int currentLength = 0;
        for (int i = 0 , start = 0; i < n; ++i) {
            if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) >= start) {
                start = map.get(s.charAt(i)) + 1;
            }
            map.put(s.charAt(i), i);
            currentLength = i - start + 1;
            maxLength = Math.max(currentLength, maxLength);
        }
        return maxLength;
    }
}

Python solution

class Solution :
    def  lengthOfLongestSubstring(self, s) :
        n = len(s)
        if (n == 0) :
            return 0
        map =  dict()
        maxLength = 0
        currentLength = 0
        i = 0
        start = 0
        while (i < n) :
            if ((s[i] in map.keys()) and map.get(s[i]) >= start) :
                start = map.get(s[i]) + 1
            map[s[i]] = i
            currentLength = i - start + 1
            maxLength = max(currentLength,maxLength)
            i += 1
        return maxLength

Source: LeetCode # 3