algoadvance

Leetcode 3. Longest Substring Without Repeating Characters

Problem Statement

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

Clarifying Questions

  1. Input Constraints:
    • What is the length range of the input string s?
      • Typical constraints might range from 0 to 10^5 characters.
  2. Character Set:
    • What type of characters does the string contain?
      • Normally, this can be assumed to be standard ASCII characters.
  3. Edge Cases:
    • How should the function behave for empty input strings?
      • Typically, the result should be 0 for an empty string.
    • Should the solution handle large input strings efficiently?
      • Yes, it is expected to handle up to the maximum constraint efficiently.

Strategy

We’ll use the Sliding Window technique combined with a HashMap to efficiently track the characters and their most recent positions. Here’s the plan:

  1. Initialize Variables:
    • An int variable maxLength for the result.
    • An int variable start to track the starting index of the current window.
    • A HashMap<Character, Integer> to store the most recent position of each character.
  2. Iterate through the String:
    • For each character in the string, check if it’s already in the HashMap.
    • If the character is in the HashMap and its position is within the current window (start to the current index), update start to be one more than this position to ensure no duplicates.
    • Update the HashMap with the current position of the character.
    • Calculate the length of the current window and update maxLength if this window is larger.

Code

import java.util.HashMap;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int maxLength = 0;
        int start = 0;
        HashMap<Character, Integer> charIndexMap = new HashMap<>();

        for (int end = 0; end < s.length(); end++) {
            char currentChar = s.charAt(end);

            // If character is in the map and its index is within the current window
            if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= start) {
                start = charIndexMap.get(currentChar) + 1;
            }

            charIndexMap.put(currentChar, end);
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test cases
        System.out.println(sol.lengthOfLongestSubstring("abcabcbb")); // Output: 3
        System.out.println(sol.lengthOfLongestSubstring("bbbbb"));    // Output: 1
        System.out.println(sol.lengthOfLongestSubstring("pwwkew"));   // Output: 3
        System.out.println(sol.lengthOfLongestSubstring(""));         // Output: 0
        System.out.println(sol.lengthOfLongestSubstring("abcdefg"));  // Output: 7
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string:

This approach efficiently finds the length of the longest substring without repeating characters by maintaining a sliding window over the string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI