Two Pointers on string

Question

Given a string, implement a solution using the two-pointer technique to find the longest substring without repeating characters. The function should return the length of this substring. For example, given the input "abcabcbb", the output should be 3, corresponding to the substring "abc".

Codemia · Accepted Answer

In this problem, we want to find the longest substring without repeating characters from a given string. The two-pointer technique is particularly suitable here because it allows us to maintain a dynamic range (or window) of characters as we iterate through the string. As we explore the string, one pointer (`start`) will indicate the beginning of the current substring, while the other pointer (`end`) will iterate through the string to check for repeating characters. When a duplicate character is found, we can adjust the `start` pointer to exclude the first occurrence of the duplicate, effectively shrinking our window until all characters are unique again. This approach is efficient and allows us to scan the string in linear time.

1. Initialize two pointers: `start` at 0 and `end` at 0, and a variable `max_length` to keep track of the longest substring length.
2. Use a set to keep track of characters in the current substring.
3. Iterate with the `end` pointer through each character in the string:
   - If the character at `end` is not in the set, add it to the set and update `max_length` to be the maximum of its current value and the size of the set.
   - If the character is already in the set, this indicates a repeat: increment the `start` pointer until the character at `end` can be added again, removing characters from the set as the `start` pointer moves.
4. Continue this process until `end` reaches the end of the string. 
5. Return `max_length` as the result.

**Example:** For the input string "abcabcbb":
- Start with `start = 0`, `end = 0`, `max_length = 0`, and an empty set.
- Add 'a', then 'b', then 'c' to the set.
- When `end` reaches the second 'a', move `start` to 1, remove 'a' from the set, then continue.
- The longest substring without repeating characters is "abc", with a length of 3.

```python
def length_of_longest_substring(s: str) -> int:
    char_set = set()
    max_length = 0
    start = 0

for end in range(len(s)):
        while s[end] in char_set:
            char_set.remove(s[start])
            start += 1
        char_set.add(s[end])
        max_length = max(max_length, end - start + 1)

return max_length
```

The time complexity of this solution is O(n), where n is the length of the string. This is because each character is processed at most twice: once when added and once when removed from the set. The space complexity is O(min(n, m)), where m is the size of the character set (e.g., 128 for ASCII). This accounts for the space used by the set storing characters of the current substring.

1. **Empty String**: If the input string is empty, return 0 since there are no characters.
2. **All Unique Characters**: For a string like "abcdef", the longest substring is the whole string, hence return its length (6).
3. **All Same Characters**: For a string like "aaaa", the longest substring without repeating characters is just one character, so return 1.
4. **Long Repeating Patterns**: For a string like "abcabcabc", the expected output is 3, corresponding to "abc".
5. **Single Character**: For input like "b", the result should be 1.

Two Pointers on string

Visa

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Visa Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string