In this article, we 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

import java.util.HashSet;  
import java.util.Set;

public class LongestDistinctChars_BruteForce {  
    static String bruteforce(String s) {
        int l = 0, i = 0, j = 0;
        int n = s.length();

        for (; i < n; i++) {
            for (j = i+1; j <= n; j++) {
                if (isUnique(s, i, j)) l = Math.max(l, j-i);
                else break;
            }

            if (j == n+1) break;
        }

        return s.substring(i, i+l);
    }

    static boolean isUnique(String s, int i, int j) {
        HashSet<Character> set = new HashSet<>();
        for (int k = i; k < j; k++) {
            if (set.contains(s.charAt(k))) return false;
            set.add(s.charAt(k));
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println(bruteforce("HelloKoding"));
    }
}
  • 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

import java.util.HashSet;  
import java.util.Set;

public class LongestDistinctChars_SlidingWindow {  
    static String slidingWindow(String s) {
        int n = s.length();
        int l = 0, i = 0, j = 0;
        Set<Character> chars = new HashSet<>();

        while(i < n && j < n) {
            if(!chars.contains(s.charAt(j))) {
                chars.add(s.charAt(j++));
                l = Math.max(l, j-i);
            } else {
                chars.remove(s.charAt(i++));
            }
        }

        return s.substring(i, i+l);
    }

    public static void main(String[] args) {
        System.out.println(slidingWindow("HelloKoding"));
    }
}
  • Output
Koding

  • Time complexity: O(n)

  • Space complexity: O(n)

Algorithm