Quick Overview

Find the length of the longest contiguous string segment with no repeated characters, including spaces and symbols.

Measure the Longest Segment of Distinct Characters

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Other

### Problem Given the string `text`, return the greatest length of a contiguous substring whose characters are all different. Return a length, not the substring itself. Characters retain their usual identity: an uppercase letter and its lowercase counterpart are different characters. Digits, punctuation, and spaces participate in the same duplicate check as letters. A subsequence formed by skipping positions does not qualify. Preserve the callable interface of `lengthOfLongestSubstring`: one string argument and an integer result. ### Examples **Example 1** ```text Input: text = "abcaefb" Output: 5 ``` The contiguous segment `"bcaef"` has five different characters. No six-character segment avoids a repeated character. **Example 2** ```text Input: text = "zzzz" Output: 1 ``` Every segment longer than one character repeats `z`. ### Constraints - The input has between `0` and `100000` characters. - Its characters are English letters, digits, symbols, and spaces. - An empty input has answer `0`.

Overview: Find the length of the longest contiguous string segment with no repeated characters, including spaces and symbols.

Given a string `text`, return the length of the longest contiguous substring of `text` in which no character appears more than once. Return the length as an integer, not the substring itself. Characters are compared exactly as they are: - An uppercase letter and its lowercase counterpart are different characters (`'a'` and `'A'` may both appear in the same window). - Digits, punctuation, symbols and the space character take part in the same duplicate check as letters. - Only contiguous substrings count. A subsequence formed by skipping positions does not qualify. If `text` is empty, return `0`. **Example 1** ``` Input: text = "abcaefb" Output: 5 ``` The substring `"bcaef"` has five different characters. Every substring of length six contains a repeated character. **Example 2** ``` Input: text = "zzzz" Output: 1 ``` Every substring longer than one character repeats `z`. **Constraints** - `0 <= text.length <= 100000` - `text` consists of English letters, digits, symbols and spaces (printable ASCII, character codes 32 to 126). - The answer is a single non-negative integer no larger than `text.length`; it always fits in a 32-bit signed integer.

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

  1. Checking every substring separately repeats a lot of work. Try keeping one window that you extend to the right one character at a time.
  2. 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?
  3. 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

d={} ln=float('-inf') start=0 for i in range(len(text)): if text[i] not in d: d[text[i]]=i else: start=d[text[i]]+1 ln=max(ln,i-start+1) return ln

Answer by ksvd1234

def lengthOfLongestSubstring(text: str) -> int: char_index = {} left = 0 max_length = 0 for right in range(len(text)): char = text[right] # Move left pointer if character is repeated if char in char_index and char_index[char] >= left: left = char_index[char] + 1 # Update the character's latest index char_index[char] = right # Update maximum window length max_length = max(max_length, right - left + 1) return max_length

Answer by Coderka14

#include using namespace std; class Solution { public: int lengthOfLongestSubstring(string text) { int n = text.size(); unordered_set st; int left = 0; int ans = 0; for (int right = 0; right < n; right++) { while (st.find(text[right]) != st.end()) { st.erase(text[left]); left++; } st.insert(text[right]); ans = max(ans, right - left + 1); } return ans; } }; /* class Solution { public: int lengthOfLongestSubstring(string s) { // vector chars(128); // int left = 0; // int right = 0; // int res = 0; // while (right < s.length()) { // char r = s[right]; // chars[r]++; // while (chars[r] > 1) { // char l = s[left]; // chars[l]--; // left++; // } // res = max(res, right - left + 1); // right++; // } // return res; // unordered_mappos; vectorlastPos(245,-1); int left = 0; int ans = 0; for(int right=0;right<s.size();right++) { if(lastPos[s[right]]!=-1) left = max(left,lastPos[s[right]]); ans = max(ans , right-left+1); lastPos[s[right]] = right + 1; // next substring start from next index } return ans; } }; */

Answer by takuma.takezawa117

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: counter = {} l = 0 res = 0 for r in range(len(s)): counter[s[r]] = counter.get(s[r], 0) + 1 while l < r and counter[s[r]] > 1: counter[s[l]] -= 1 l += 1 res = max(res, r - l + 1) return res

Answer by lucid

class Solution { public: int lengthOfLongestSubstring(string s) { map last; int l = 0, ans = 0; for (int r = 0; r < s.size(); r++) { if (last.count(s[r])) { l = max(l, last[s[r]] + 1); } last[s[r]] = r; ans = max(ans, r-l+1); } return ans; } };

Loading coding console...

Show the approach

Approach

Use a sliding window [start, i] that always contains distinct characters, and a map from each character to the index where it was last seen. Scan i from left to right. If text[i] was last seen at an index prev that is inside the current window (prev >= start), the window can no longer include that earlier copy, so move start to prev + 1. If prev is before start, that earlier copy is already outside the window and start stays put; this check is what keeps start from jumping backward on inputs like "abba". Record i as the last index of text[i], then the window [start, i] is valid and its length i - start + 1 is a candidate for the answer. Every valid substring ending at i is contained in the window computed for i, because start is the smallest index that keeps the window duplicate-free, so taking the maximum over all i gives the longest one. Each character is visited once and each map operation is constant time.

Time complexity:
O(n)
Space complexity:
O(min(n, k)) where k is the alphabet size (at most 95 printable ASCII characters)