Algorithms – Part 7: Longest Substring Without Repeating Characters: Brute Force

This is an algorithm question from earlier this year, and let’s revisit the problem and analyze its structure once more.

Since I started exploring new career opportunities, I’ve begun learning algorithmic coding questions in the style of LeetCode. I’ve revisited the more complex sections I wrote about in this blog earlier this year.

(allUnique(s, i, j)) ans = Math.max(ans, j - i)

Question:

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

Brute force 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);
    }
}

A step-by-step explanation:

In the code provided, the goal is to find the length of the longest substring without repeating characters. To achieve this, the code uses a brute-force approach with nested loops. Here’s a step-by-step explanation:

1. The outer loop, controlled by i, iterates through each character in the input string s.
2. The inner loop, controlled by j, iterates through all possible substrings that start at the current character i.
3. The allUnique function is called to check if the substring from index i to j contains all unique characters. The function uses a set to keep track of characters encountered in the substring.
4. If the allUnique function returns true, it means the substring contains all unique characters, and we want to update the answer. Here’s why ans = Math.max(ans, j - i) is used:
   • j - i represents the length of the current substring that starts at index i and ends at index j.
   • ans is used to keep track of the length of the longest substring without repeating characters found so far. By comparing the current substring’s length (j - i) with the current maximum (ans), the code ensures that ans stores the maximum length.
   • If the current substring is longer than the previously recorded maximum, ans is updated to store the length of the new longest substring.
5. The outer loop continues its iteration, and the process is repeated for each character in the input string.
6. Finally, the value of ans represents the length of the longest substring without repeating characters in the entire string.

To summarize, the mechanism if (allUnique(s, i, j)) ans = Math.max(ans, j - i) checks if the current substring is valid (contains all unique characters) and, if it is, updates the ans variable to store the length of the longest such substring found so far. The j - i part calculates the length of the current substring for this comparison.