LeetCode 1624: Largest Substring Between Two Equal Characters

Explanation

To solve this problem, we can iterate over the given string s and keep track of the first and last occurrence of each character. For each character, we calculate the length of the substring between its first and last occurrence. We update the maximum length found so far. If no substring is found, we return -1.

• We can use a hashmap to store the first occurrence of each character.
• We iterate over the string to update the last occurrence of each character.
• For each character, we calculate the length of the substring between its first and last occurrence.
• We update the maximum length found so far.

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s.

Space Complexity

The space complexity of this solution is O(1) since the hashmap stores at most 26 lowercase English letters.

class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        int[] firstIndex = new int[26];
        int maxLength = -1;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (firstIndex[c - 'a'] == 0) {
                firstIndex[c - 'a'] = i + 1;
            } else {
                maxLength = Math.max(maxLength, i - firstIndex[c - 'a']);
            }
        }
        
        return maxLength;
    }
}