Skip to main content

14. Longest Substring Without Repeating Characters

mediumAsked at Gojek

Find the length of the longest substring of a string that contains no repeated characters.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string s, find the length of the longest substring without repeating characters.

Constraints

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces

Examples

Example 1

Input
s = "abcabcbb"
Output
3

Example 2

Input
s = "bbbbb"
Output
1

Approaches

1. Brute force

Try every substring and use a set to check uniqueness.

Time
O(n^3)
Space
O(min(n, alphabet))
let best = 0;
for (let i = 0; i < n; i++)
  for (let j = i; j < n; j++) {
    const set = new Set(s.slice(i, j+1));
    if (set.size === j - i + 1) best = Math.max(best, j - i + 1);
  }

Tradeoff:

2. Sliding window with hash

Track each char's last seen index; jump the left pointer past any repeat. One pass.

Time
O(n)
Space
O(min(n, alphabet))
function lengthOfLongestSubstring(s) {
  const last = new Map();
  let l = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    if (last.has(c) && last.get(c) >= l) l = last.get(c) + 1;
    last.set(c, r);
    best = Math.max(best, r - l + 1);
  }
  return best;
}

Tradeoff:

Gojek-specific tips

Gojek interviewers like clean sliding-window writeups because deduplication shows up in their multi-service event pipelines, like dropping repeated push-notification keys per device.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Longest Substring Without Repeating Characters and other Gojek interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →