## Revisit the longest-substring algorithms

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:

- The outer loop, controlled by
`i`

, iterates through each character in the input string`s`

. - The inner loop, controlled by
`j`

, iterates through all possible substrings that start at the current character`i`

. - 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. - 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.

- The outer loop continues its iteration, and the process is repeated for each character in the input string.
- 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.