Practice › Sliding Window
Longest Substring Without Repeating Characters
Medium · Sliding Window · Asked at Amazon, Google, Microsoft, Adobe, Flipkart
Print the length of the longest substring with no repeating characters.
Input
One string s (printable characters without spaces).
Output
The length.
Constraints
- 1 ≤ |s| ≤ 10^5
Example 1
Input
abcabcbb
Output
3
Example 2
Input
bbbbb
Output
1
Hints
- Keep a window [l, r] with no repeated character, growing r one step at a time.
- Remember the last index of every character. If s[r] was last seen inside the window, jump l to just after it.
Approach
Store last[c], the most recent index of character c. When s[r] was seen at an index ≥ l, the window has a repeat, so move l = last[s[r]] + 1. l only moves forward. Update last[s[r]] = r and the best length r − l + 1. A 256-entry array covers every printable character.
Complexity: O(n) time · O(1) space (256 entries)
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
vector<int> last(256, -1);
int best = 0, l = 0;
for (int r = 0; r < (int)s.size(); r++) {
unsigned char c = s[r];
if (last[c] >= l) l = last[c] + 1;
last[c] = r;
best = max(best, r - l + 1);
}
cout << best << "\n";
return 0;
}Python solution
s = input().strip()
last = {}
best = l = 0
for r, ch in enumerate(s):
if last.get(ch, -1) >= l:
l = last[ch] + 1
last[ch] = r
best = max(best, r - l + 1)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int[] last = new int[65536];
Arrays.fill(last, -1);
int best = 0, l = 0;
for (int r = 0; r < s.length(); r++) {
char c = s.charAt(r);
if (last[c] >= l) l = last[c] + 1;
last[c] = r;
best = Math.max(best, r - l + 1);
}
System.out.println(best);
}
}Solve Longest Substring Without Repeating Characters online · All practice problems