# HelloKoding

Practical coding guides

# Longest Substring Without Repeating Characters

In this article, you will learn to analyze and resolve the Longest substring without repeating characters problem by using a hash table as a sliding window to check a condition while 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

LongestDistinctChars_BruteForce.java

``````package com.hellokoding.algorithm;

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;
}

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

LongestDistinctChars_SlidingWindow.java

``````package com.hellokoding.algorithm;

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))) {
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)