medium Longest Substring Without Repeating Characters

Problem Statement

Given a string, identify the length of its longest segment that contains distinct characters. In other words, find the maximum length of a substring that has no repeating characters.

Examples:

1. Example 1:

   • Input: "abcdaef"
   • Expected Output: 6
   • Justification: The longest segment with distinct characters is "bcdaef", which has a length of 6.

2. Example 2:

   • Input: "aaaaa"
   • Expected Output: 1
   • Justification: The entire string consists of the same character. Thus, the longest segment with unique characters is just "a", with a length of 1.

3. Example 3:

   • Input: "abrkaabcdefghijjxxx"
   • Expected Output: 10
   • Justification: The longest segment with distinct characters is "abcdefghij", which has a length of 10.

Constraints:

• 0 <= s.length <= 5 * 10⁴
• s consists of English letters, digits, symbols and spaces.

Pattern: Variable-size sliding window for "longest substring with all unique characters." Recognition: maximize length of a contiguous segment where a set-based invariant holds (no duplicates). Template: grow end; while the new char is already in the window set, remove s[start] and advance start (a while, not a single step); then add the new char and update best length. Same skeleton as "at most K distinct" (use a frequency map; shrink when distinct count exceeds K).

When-not: non-contiguous subsequence → DP/LIS-style, not a window. "Longest substring with all identical characters" is a simple run-length scan. Empty string → 0 (constraints allow length 0).

Complexity: each index enters/leaves the set at most once → O(n) time; space O(min(n, |Σ|)) for the character set (bounded alphabet → O(1) relative to |Σ|).

Algorithm Description:

Iterate with two pointers and a HashSet of characters inside the current window. Advance end; if s[end] is already in the set, remove characters from start one by one until the duplicate is gone; then insert s[end] and update the max window length. The code's if/else form keeps end fixed while shrinking, which is equivalent to an inner while-loop.

1. Initialization: Begin with two pointers, start and end, both at the start of the string. The hashset will initially be empty.

2. Sliding Window Expansion: Progressively move the end pointer to the right until you come across a character that's already in the hashset, indicating a repetition.

3. Adjusting Start Pointer: Upon detecting a repeated character, increment the start pointer by one position and remove the character at the start position from the hashset. This action ensures that the window only contains unique characters.

4. Result Calculation: At each step, calculate the length of the current window (from start to end). Keep track of the maximum length observed.

By the end of this process, the maximum length observed will be the length of the longest segment of unique characters in the string.

Algorithm Walkthrough:

Given the string "abrkaabcdefghijjxxx":

• Initialize start and end to 0, and an empty hashset.
• As you move end from 0 to the end of the string:
  • When end is at position 4 (character 'a'), since 'a' is already in the hashset, we will remove the character at position 0 ('a') from the hashset and move start to position 1.
  • Continue this process, always ensuring the characters between start and end are unique.
  • Calculate the length of the segment at each step (start -> end) and update the maximum length.
• The maximum length observed will be 10, corresponding to the segment "abcdefghij".

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

import java.util.HashSet;

public class Solution {

  public int lengthOfLongestSubstring(String s) {
    HashSet<Character> set = new HashSet<>();
    int maxLength = 0, start = 0, end = 0;

    // Traverse the string with the end pointer
    while (end < s.length()) {
      // If the character is not in the set, it's a unique character for the current substring
      if (!set.contains(s.charAt(end))) {
        set.add(s.charAt(end));
        maxLength = Math.max(maxLength, end - start + 1);
        end++;
      } else {
        // If we find a repeating character, remove the character at the start pointer and move the start pointer
        set.remove(s.charAt(start));
        start++;
      }
    }

    return maxLength;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.lengthOfLongestSubstring("abcdaef")); // Expected: 6
    System.out.println(sol.lengthOfLongestSubstring("aaaaa")); // Expected: 1
    System.out.println(sol.lengthOfLongestSubstring("abrkaabcdefghijjxxx")); // Expected: 10
  }
}

Time Complexity

1. While Loop: The algorithm uses a sliding window approach with two pointers, start and end. In the worst-case scenario, both pointers traverse the entire length of the string. Since each pointer can move from the beginning to the end of the string, the time complexity is O(2n), where n is the length of the string. However, in big O notation, constants are dropped, so the time complexity is O(n).

2. HashSet Operations: The operations of adding, deleting, and checking for the existence of an element in a HashSet (or Set in some languages) are O(1) on average. Therefore, these operations don't add any significant overhead to the time complexity.

Combining the above points, the overall time complexity of the algorithm is O(n).

Space Complexity

1. HashSet: The space complexity is determined by the size of the HashSet. In the worst-case scenario, the HashSet will store all unique characters of the string. Since the set of possible characters is fixed (assuming the ASCII character set, which has 128 characters, or the extended ASCII set, which has 256 characters), the space complexity is O(min(n, m)), where n is the length of the string and m is the character set size (either 128 or 256). For most strings, n will be much larger than m, so the space complexity is effectively O(m), which is a constant.

Therefore, for a fixed alphabet the space is O(|Σ|) (constant w.r.t. string growth); writing it as O(1) is acceptable in interviews only when you state the alphabet is bounded. Prefer stating O(min(n, |Σ|)).

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Solution Longest Substring Without Repeating Characters medium

Why this concept exists (judgment layer)

Longest substring with unique characters is the set-invariant variable window: grow end; while duplicate, eject from start. Same skeleton as 'at most K distinct' with K=all-unique (set size = window length).

Worked example with complexity derivation

s='abcdaef':
Grow abcd; at second 'a' shrink remove 'a' at 0 → 'bcd' then add … → 'bcdaef' length 6.
s='aaaaa' → max 1. s='abrkaabcdefghijjxxx' → 'abcdefghij' length 10.
Each index enters/leaves set ≤ once → O(n) time; space O(min(n,|Σ|))
(ASCII → O(1) w.r.t. growth if |Σ| fixed).
Map last-index jump: can advance start to last[c]+1 in one step — still O(n).

Pattern + when-NOT / named alternative

PATTERN: expand end; while s[end] in window set, remove s[start], start++. WHEN NOT: non-contiguous subsequence → DP/LIS style. All identical longest run → run-length not uniqueness set. Empty string → 0 (length 0 allowed).

Edge case / failure mode

Edges: empty → 0; single char; all unique → n; spaces/symbols in alphabet. Failure: if instead of while shrink once — duplicate may remain if not the start char. Code's if/else form keeps end fixed while shrinking — equivalent to inner while.

Hostile-panel drills (defend the decision)

Q1. State space carefully.
Model answer: O(min(n,|Σ|)); for fixed ASCII say O(|Σ|) constant w.r.t. n — prefer writing min form.

Q2. Why O(n) not O(n²)?
Model answer: start and end each move at most n times; set ops average O(1).

Q3. Sibling with K distinct?
Model answer: Same expand/shrink; shrink when distinct count > K using frequency map.