Longest Substring Without Repeating Characters - LeetCode Solution and Approach

 

 3. Longest Substring Without Repeating Characters - LeetCode - Medium

Solve this problem in LeetCode

Problem Description:

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.

Approach:

The problem is to find maximum length of substring without duplicate characters. So, in other words, we need to find the maximum length of sliding window without duplicate characters.

• We can use Map to keep track of duplicates Characters but I will take int array to store indexes of characters.
• We will iterate through the characters of string and if we found a duplicate character, we will set the starting pointer (i) of sliding window to index of duplicate character (that is stored in array) or keep i if i is at greater index.
• We will update the index of the current character and store it in array.
• We will calculate the length of the sliding window  and store the maximum length in a variable say maxL.
• We will increase the right pointer by 1 and keep iterating.
• We will get the answer in maxL.

JAVA:

Time Complexity : 0(n)

Space Complexity: 0(1)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = 0, j = 0, l = s.length(), maxL = 0;
        int[] chars = new int[128];
        while (j < l) {
            if (chars[s.charAt(j)] != -0) // if we find duplicate character 
                i = Math.max(i, chars[s.charAt(j)]); // then set starting pointer (i) as index of duplicate character, or keep i if i is greater 
            chars[s.charAt(j)] = j + 1; // update index of current character
            maxL = Math.max(maxL, j - i + 1); // set maxL to size of sliding-window or keep maxL if maxL is greater
            j++;
        }
        return maxL;
    }
}

Keep Learning and Practicing with Programming Chaska !!!