Finding the Length of the Longest Substring without repeating characters

Question

I kind of have an understanding of this algorithm as a whole, but how is Math.max being used to output the correct substring?

And how is the check repetition function actually checking each individual character for the match?

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        
         int n = s.length();
         int res = 0;
            for(int i = 0; i < n; i++){
                for(int j = i; j < n; j++){
                    if(checkRepetition(s,i,j)){
                        res = Math.max(res, j - i + 1);
                    }
                }
            }
        return res;
    }
    
    private boolean checkRepetition(String s,int start,int end){
        int []chars = new int [128];
        
            for(int i = start; i <= end; i++){
                char c = s.charAt(i);
                chars[c]++;
                
                if(chars[c] > 1){
                    return false;
                }
            }
        return true;
    }
}

Answer 1

Your current, brute-force solution generates indices of each and every substring and then checks whether it contains repeated characters.

By doing so, you are repeating the same calculations multiple time. Instead of revisiting the same parts of the string over and over, we can perform this check only once and then reuse the results.

I don't know if there are some constraints regarding the input in this challenge, but creation of an array of length 128 seems fishy because it exceeds the range of digits and lower-case/upper-case English letters. If you print on the console characters that correspond to let's say 0, 10 and 127 you will not see anything meaningful on the console.

And overall time complexity is quadratic O(n ^ 2) (considering the time complexity of the method checkRepetition() to be constant because it can perform at most 128 iterations).

This problem can be solved in a linear time O(n).

And it doesn't require any assumptions. The algorithm introduced below is based on the suggestion by @Andrey B. Panfilov provided in the comments.

To find the longest substring not containing characters that are repeated withing the substring, we need to iterate over the given string and store previously encountered characters for a current non-repeated substring. For that, we can use a HashSet (denoted as seen).

We also need to maintain an index pointing to the beginning of the current substring (denoted as left).

While iterating, we are trying to incorporate every new character to the current substring, and if seen.add() would return false that means that we've hit a duplicate, and it means that we've done with the previous substring. Now we need to move the left index to the right to position one index beyond the previous occurrence of the character at the end of the current substring (at the index right). While moving the left index we also have to remove corresponding characters str.charAt(left) from the set.

To store the maximum length of the non-repeated substring we need to maintain a variable which has to be updated at the end of each iteration.

That's how it can be implemented:

public static int lengthOfLongestSubstring(String str) {
    
    Set<Character> seen = new HashSet<>();
    
    int left = 0;
    int maxSub = 0;
    
    for(int right = 0; right < str.length(); right++) {
        char next =  str.charAt(right);
        
        if (!seen.add(next)) {
            while (str.charAt(left) != next) {
                seen.remove(str.charAt(left++));
            }
            left++;
        }
        
        maxSub = Math.max(right + 1 - left, maxSub);
    }
    return maxSub;
}

main()

public static void main(String[] args) {
    System.out.println(lengthOfLongestSubstring(""));              // 0
    System.out.println(lengthOfLongestSubstring("a"));             // 1
    System.out.println(lengthOfLongestSubstring("aa"));            // 1
    System.out.println(lengthOfLongestSubstring("abc"));           // 3
    System.out.println(lengthOfLongestSubstring("abccb"));         // 3
    System.out.println(lengthOfLongestSubstring("abccfghijklhl")); // 8
}

Output:

0   // ""
1   // "a"
1   // "aa"
3   // "abc"
3   // "abccb"
8   // "abccfghijklhl"

Answer 2

but how is Math.max being used to output the correct substring?

Math.max is used to only get the maximum length and not the substring itself. To get the maximum length substring you need to create a string variable and update it accordingly as:

if (j-i+1 > res) {
   res = j-i+1
   maxString = s.subsring(i, j+1)
}

And how is the check repetition function actually checking each individual character for the match?

Look at int[] chars = new int[128] and chars[c]++

The second part increments the number of times a character occurs in a string.

For example in your input string lets say the character 'z' appears twice then the chars array at the location 122 is incremented because the character 'z' is equivalent to integer 122 in ascii table. So if chars[122] > 1, then there is a repetition of 'z'. Simple. That's what the next block

if(chars[c] > 1){
   return false;
}

is doing.