Table of contents


Given problem

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

Example 1:
    Input: "abcabcbb"
    Output: 3 
    Explanation: The answer is "abc", with the length of 3. 

Example 2:
    Input: "bbbbb"
    Output: 1
    Explanation: The answer is "b", with the length of 1.

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


Using brute force algorithm

Based on that each size runs from 1 to the length of the input string, we will get the corresponding substring. To check whether a substring contains the duplicated characters or not, we will use a char array to count the number of characters.

public static int lengthOfLongestSubstring(String s) {
    int len = s.length();
    int[] ints = new int[26];
    int maxLength = Integer.MIN_VALUE;

    for (int size = 1; size < len; ++size) {
        for (int i = 0; i <= len - size; ++i) {
            boolean isDuplicated = false;
            String substring = s.substring(i, i + size);

            // input data into an ints array
            for (int j = 0; j < substring.length(); ++j) {
                ints[substring.charAt(j) - 'a']++;
            }

            for (int j = 0; j < 26; ++j) {
                if (ints[j] > 1) {
                    isDuplicated = true;
                    break;
                }
            }

            if (!isDuplicated) {
                maxLength = Math.max(maxLength, substring.length());
            }

            Arrays.fill(ints, 0);
        }
    }

    return maxLength;
}

The complexity of this solution:

  • Time complexity: O(n^3)
  • Space complexity: O(26)


Using sliding window technique

Because our result string is a substring, it is not a subsequence. So we can use the sliding window technique to overcome this problem.

public int lengthOfLongestSubstring(String s) {
    int windowStart = 0;
    int size = s.length();
    Map<Character, Integer> mpCountCharacters = new HashMap<>();
    int maxLength = 0;

    for (int windowEnd = 0; windowEnd < size; ++windowEnd) {
        char rightChar = s.charAt(windowEnd);
        if (mpCountCharacters.containsKey(rightChar)) {
            windowStart = Math.max(windowStart, mpCountCharacters.get(rightChar) + 1);
        }

        mpCountCharacters.put(rightChar, windowEnd);
        maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
    }

    return maxLength;
}

The complexity of this solution:

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


Wrapping up

  • Understanding about the requirements and some particular points to use Sliding Window technique.


Refer:

https://leetcode.com/problems/longest-substring-without-repeating-characters/