Road to Google – Part 5 Longest Substring Without Repeating Characters: Brute Force and Optimal Solution

Question:

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

This question asks you to find the longest substring within a string. Let’s say you’ve given this string shown in image 01.

The unique substrings you can find in the string are “abc” and “cab”. And the length of both is 3, so the answer to this question is 3.

Substring vs Subsequence:

Here, you may want to ask a question – is it contiguous? So what does it mean? Well, as you can see in the below image 03, a substring is a contiguous series of unique characters, while a subsequence contains a single character that doesn’t necessarily have to be a contiguous series of unique characters. This time, we’ll only focus on the substring.

Our test cases:

Here are our test cases and what needs your attention is the last one. There are two substrings, “abc” and “cbda”, where c overlaps both. In this case, the longest substring is the latter one.

Our brute force solution:

Here, you’ve given this string, and let’s think about how we can solve this problem.

We have the int variable that keeps track of the longest substring and we’ll start loop iteration from “a”.

Starting from a, ask your self “have you seen ‘a’ before?” – No. So, we’ll add ‘a’ to the cache and update the longest to 1.

And we’ll keep iterating through the string up to the first ‘c’ and at this point, the longest is 3 and chance has a, b, and c.

And when we raches the second ‘b’, ask yourself “have you seen ‘b’ before?” – Yes you did, and the first iteration ends here.

And the next iteration starts from ‘b’ and it ends up with the longest with 2.

The next iteration starts from ‘c’ and it ends up with the longest with 3.

The next iteration starts from ‘b’ and it ends up with the longest with 4. And sat this point, you already know that 4 is the longest number.

The rest of the iteration doesn’t need any description, so I’ll skip it. Now, let’s see how we can solve this problem with actual code.

Coding solution:

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

public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (allUnique(s,i,j)) ans = Math.max(ans, j - i);
            }
        }
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
    
    public static void main(String[] args) {
        String v = "abccbda";
        LongestSubstring longestSubstring = new LongestSubstring();
        int answer = longestSubstring.lengthOfLongestSubstring(v);
        System.out.println("The answer is: " + answer);
    }
}

Let’s take a look at every line:

In the lengthOfLongestSubstring method, the length of the string s is calculated and stored in the variable n.

int n = s.length();

An integer variable ans is initialized to 0 to store the length of the longest substring without repeating characters.

int ans = 0;

The outer for loop iterates over the string s starting from index i = 0 to n-1 to explore all possible substrings of s.

*It’s n-1 because, in the programming world, an array always starts from 0.

The inner for loop iterates over the string s starting from i+1 to n to explore all substrings ending at index j.

For each pair of i and j, the allUnique method is called to check if the substring from start to end is unique.

for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (allUnique(s,i,j)) ans = Math.max(ans, j - i);
     }
}
return ans;

The allUnique method takes in a string s and two integer values start and end as parameters and returns a boolean value indicating whether the substring is unique or not.

The method creates a Set of Character objects named set and iterates over the substring from start to end-1.

For each character ch in the substring, the method checks if the character is already present in the set. If it is, then the method returns false indicating that the substring is not unique.

If the character ch is not present in the set, it is added to the set.

After the loop, the method returns true indicating that the substring is unique.

public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }

If the substring is unique, the length of the substring is calculated and stored in j-i. This value is compared with the current value of ans and if it is greater, ans is updated to the new value.

After the inner loop, the outer loop continues with the next value of i.

After both loops, the final value of ans is returned as the length of the longest substring without repeating characters.

for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (allUnique(s,i,j)) ans = Math.max(ans, j - i);
     }
}
return ans;

Executed result:

$ java LongestSubstring
The answer is: 4