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

CodePudding user response：

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[126] 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.

CodePudding user response：

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.

Firstly, we need to calculate frequencies of every character in the string.

Then we can use the logic that is somewhat similar to the Kadane’s algorithm which is used for finding the maximum subarray sum. We need to maintain two variables representing the current substring length and the maximum substring length that has been encountered so far.

public int lengthOfLongestSubstring(String str) {

    Map<Character, Integer> frequencyByChar = getFrequencies(str);
    
    int maxSub = 0;
    int curSub = 0;
    
    for(int i = 0; i < str.length(); i  ){
        char next = str.charAt(i);
        
        if (frequencyByChar.get(next) > 1) {
            curSub = 0;
            continue;
        }
        
        curSub  ;
        maxSub = Math.max(curSub, maxSub);
    }
    return maxSub;
}

public static Map<Character, Integer> getFrequencies(String str) {
    Map<Character, Integer> frequencyByChar = new HashMap<>();
    for (int i = 0; i < str.length(); i  ) {
        char next = str.charAt(i);
        frequencyByChar.merge(next, 1, Integer::sum);
    }
    return frequencyByChar;
}

Instead of map Map<Character, Integer> we can use a map Map<Character, Boolean> (or even array boolean[] if there's constraint that input would contain only, for instance, lower-case English letters), because we are not interested in the actual number of occurrences for each letter, all we need to know whether it's repeated or not.

That's how it can be done:

public int lengthOfLongestSubstring(String str) {

    Map<Character, Boolean> isRepeatedByChar = getIsRepeatedMap(str);
    
    int maxSub = 0;
    int curSub = 0;
    
    for(int i = 0; i < str.length(); i  ){
        char next = str.charAt(i);
        
        if (isRepeatedByChar.get(next)) {
            curSub = 0;
            continue;
        }
        
        curSub  ;
        maxSub = Math.max(curSub, maxSub);
    }
    return maxSub;
}

public static Map<Character, Boolean> getIsRepeatedMap(String str) {
    Map<Character, Boolean> isRepeatedByChar = new HashMap<>();
    for (int i = 0; i < str.length(); i  ) {
        char next = str.charAt(i);
        isRepeatedByChar.merge(next, false, (oldVal, newVal) -> true);
    }
    return isRepeatedByChar;
}