AI ML

Longest substring without repeating characters

Asked at

Amazon

Meesho

Quince

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string, S. Find the length of the longest substring without repeating characters.

Input : S = "abcddabac" Output : 4 Explanation : The answer is "abcd" , with a length of 4.

Input : S = "aaabbbccc" Output : 2 Explanation : The answers are "ab" , "bc". Both have maximum length 2.

Input : S = "aaaa"

1 <= S.length <= 5*104
S contains only English lowercase letters.

cpp

class Solution{
  public:
    int longestNonRepeatingSubstring(string& s){
        //your code goes here
    }
};

java

class Solution {
    public int longestNonRepeatingSubstring(String s) {
        //your code goes here
    }
}

python

class Solution:
    def longestNonRepeatingSubstring(self, s):
        #your code goes here

javascript

class Solution {
    longestNonRepeatingSubstring(s) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public int LongestNonRepeatingSubstring(string s)
    {
        //your code goes here
    }
}

func longestNonRepeatingSubstring(s string) int {

}

Stuck? Show a way to structure it+

01Keep a left boundary and the latest index for each character.
02Extend the right boundary one character at a time.
03When a repeated character is inside the window, move left past its earlier index.
04Update the best window length after restoring uniqueness.

Reference answer

Maintain a window [left, right] containing no repeated character and a map from character to its latest index. When reading s[right], if it was last seen at an index at least left, set left to that index plus one. Then record its new index and maximize right - left + 1. The key detail is not moving left backwards when a duplicate lies outside the current window. Each pointer advances at most n times, so time is O(n) and space is O(min(n, alphabet)). In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would you return the substring rather than its length?
Tests: window reconstruction
How does the approach change for Unicode grapheme clusters?
Tests: string representation

Hiring now

Quince has 52 open roles right now

Also hiring: Meesho

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Development Engineer III (Mobile)
Bengaluru, Karnataka, India
Software Engineer III, Frontend (Storefront)
Palo Alto, California, United States
Software Development Engineer - 3 (Backend)
Bengaluru, Karnataka, India

Or practice this question first

Next question