Medium
Subtopics
hash-table·sliding-window·string
Companies
adobe·alation·alibaba·amazon·apple·atlassian·baidu·bloomberg·bytedance·cisco·coupang·ebay·expedia·facebook·goldman-sachs·google·huawei·microsoft·oracle·paypal·salesforce·samsung·sap·snapchat·spotify·twitch·uber·vmware·yahoo·yandex·yelp·zillow·zohoLast updated: Aug 2, 2025
The trivial solution would be to do double for loop and from each position try to find the longest substring until we see a duplicate char. This is O(n^3) solution.
classSolution {
publicintlengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
String substring = s.substring(i, j + 1);
if (isUnique(substring)) {
ans = Math.max(ans, substring.length());
}
}
}
return ans;
}
privatebooleanisUnique(String s) {
Set<Character> seen =new HashSet<>();
for (char c : s.toCharArray()) {
if (seen.contains(c)) returnfalse;
seen.add(c);
}
returntrue;
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolution:
deflengthOfLongestSubstring(self, s: str) -> int:
n: int = len(s)
ans: int =0for i in range(n):
for j in range(i, n):
if len(set(s[i:j +1])) == (j - i +1):
ans = max(ans, j - i +1)
return ans
Finding the Longest substring without repeating characters is same as finding the Longest substring with All distinct characters. So instead of K distinct characters we have to find the longest substring where all characters are distinct.
We start with a window and maintain a hashset for that window. We keep on adding chars to window and slide window to right, till they are not duplicate. If we find duplicate we keep moving the left pointer to shrink window, till we remove that duplicate char from the set. In meantime, we will keep check of the longest window.
classSolution {
publicintlengthOfLongestSubstring(String s) {
// Initialize variables Set<Character> seen =new HashSet<>();
int left = 0, ans = 0;
// Iterate over the string using the "right" pointerfor (int right = 0; right < s.length(); right++) {
// If a duplicate character is found, shrink the window by moving "left"while (seen.contains(s.charAt(right))) {
seen.remove(s.charAt(left));
left++;
}
// Add the current character to the set and update the max length seen.add(s.charAt(right));
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution:
deflengthOfLongestSubstring(self, s: str) -> int:
# Initialize variables seen: set = set()
left: int =0 ans: int =0# Iterate over the string using the "right" pointerfor right in range(len(s)):
# If the character is already in the set, shrink the window by moving "left"while s[right] in seen:
seen.remove(s[left])
left +=1# Add the current character to the set and update the max length seen.add(s[right])
ans = max(ans, right - left +1)
return ans
⏰ Time complexity: O(n). The right pointer iterates linearly over the string, processing each character exactly once. The left pointer moves forward only when duplicates are encountered. Together, this ensures linear runtime.
🧺 Space complexity: O(m) where m represents the number of distinct or unique characters in the string. We store these characters in a HashSet to manage the current valid window. In practical scenarios, m is bounded by the size of the character set being considered (e.g., English letters, digits, and special characters).
publicintlengthOfLongestSubstring(String s) {
int n = s.length();
// answer - length of longest substring with no repeating charsint ans =-1;
// frequency map of chars in window Map<Character, Integer> windowCharCnt =new HashMap<>();
int left = 0;
for(int right = 0; right < n; right++) {
char c = s.charAt(right);
windowCharCnt.put(c, windowCharCnt.getOrDefault(c, 0) + 1);
while(windowCharCnt.size() < right - left + 1) {
char leftChar = s.charAt(left);
windowCharCnt.put(leftChar, windowCharCnt.get(leftChar) - 1);
if(windowCharCnt.get(leftChar) == 0) {
windowCharCnt.remove(leftChar);
}
left++;
}
if(windowCharCnt.size() == right-left+1) {
ans = Math.max(ans, right-left+1);
}
}
return maxLen;
}
Method 3 - Sliding Window with Boolean array as set 🏆#
We can use a flag array to track the existing characters for the longest substring without repeating characters.
When we realize that substring “abcc” has dups, we can immediately abandon the whole substring and check substrings from “cdefgh”. Thus, we have the following approach:
Keep two pointers (start, end) that denotes the current substring we’re checking and both has an initial value of 0.
Each time, move forward end pointer by 1 character and use the hashset to check if the newly added character has already existed.
If not, keep moving end pointer forward.
If the new character is a duplicate one, move the start pointer all the way to pass the duplicate character and pop out all these characters from the hashset.
Repeating step 2 and output the longest substring without dup after finishing the whole string.
publicintlengthOfLongestSubstring(String s) {
if (s ==null)
return 0;
boolean[] flag =newboolean[256];
int result = 0;
int start = 0;
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
char current = arr[i];
if (flag[current]) {
result = Math.max(result, i - start);
// the loop update the new start point// and reset flag array// for example, abccab, when it comes to 2nd c,// it update start from 0 to 3, reset flag for a,bfor (int k = start; k < i; k++) {
if (arr[k]== current) {
start = k + 1;
break;
}
flag[arr[k]]=false;
}
} else {
flag[current]=true;
}
}
result = Math.max(arr.length- start, result);
return result;
}