Measure the Longest Segment of Distinct Characters
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
Overview: Find the length of the longest contiguous string segment with no repeated characters, including spaces and symbols.
Constraints
- 0 <= text.length <= 100000
- text consists of English letters, digits, symbols and spaces (printable ASCII, codes 32 to 126)
- Uppercase and lowercase forms of a letter are different characters
- The result is between 0 and text.length and fits in a 32-bit signed integer
Examples
Input: ("",)
Expected Output: 0
Input: ("a",)
Expected Output: 1
Hints
- Checking every substring separately repeats a lot of work. Try keeping one window that you extend to the right one character at a time.
- When the new character already appears inside the current window, where is the earliest position the window can start so that it is valid again?
- Remembering the most recent index of each character lets you move the window's left edge in one step, but make sure the left edge never moves backward.
Community answers
Answer by ravi.bandaru0316
Answer by ksvd1234
Answer by Coderka14
Answer by takuma.takezawa117
Answer by lucid