Problem

  • Given a string s
  • Write an algorithm to find the longest substring without repeating characters

Example

  • Input: "HelloKoding". Expected output: "Koding"

Approach: Sliding Window

  • Use a HashSet chars to manage distinct characters

  • Maintain a substring window with start index i and end index j to find the longest substring

    Iterate over the string s, add the character at s[j] to the set chars and increase j value to 1 if s[j] is not existed in chars, otherwise remove s[i] from the set and increase i value to 1

Implementation


Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)