You will learn to resolve the longest substring without repeating characters problem by using a hash table as a sliding window to check a condition when iterating over an array or string

A window is a range of element indices in an array or string. A sliding window is a window that slides its boundaries toward a direction (left/right)

Problem

  • Given a string s

  • Write an algorithm to find in s the longest substring without repeating characters

Example

  • Input: "HelloKoding", expected output: "Koding"

Approach 1: Brute force

  • Iterate over all substrings in the given string

  • At each substring, use a hash table to check if the substring has duplicated characters or not


  • Output
Koding  
  • Time complexity: O(n3)

  • Space complexity: O(n)

Approach 2: Sliding window

  • Use a hash table h as a sliding window of characters in the given string s

  • Iterate over s, at each iteration, if h is not containing the current character, then add it to h and increases the right index to 1

  • If h is containing the current character, remove it from h and increases the left index to 1


  • Output
Koding  
  • Time complexity: O(n)

  • Space complexity: O(n)

Share to social

Giau Ngo

Giau Ngo is a software engineer, creator of HelloKoding. He loves coding, blogging, and traveling. You can find him on Twitter, GitHub and LinkedIn