Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

abcabcbb

Output

3

Example 2

Input

bbbbb

Output

1

Hints

  1. Keep a window [l, r] with no repeated character, growing r one step at a time.
  2. 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