Largest Substring Between Two Equal Characters - Leetcode Solution

Problem Statement:

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.

Example 1:

Input: s = "aa" Output: 0 Explanation: The optimal substring here is an empty substring between the two 'a's.

Example 2:

Input: s = "abca" Output: 2 Explanation: The optimal substring here is "bc".

Example 3:

Input: s = "cbzxy" Output: -1 Explanation: There is no such substring.

Solution:

To solve this problem, we can use HashMap in Java. We iterate through each character of the string and if it is not in our HashMap, we add it. If it is already in the HashMap, we calculate the length of the substring between the two occurrences of the character and update our answer if this length is greater than the current max. In case, we don't find any such substring, we return -1.

Here is the Java code:

class Solution { public int maxLengthBetweenEqualCharacters(String s) { int max = -1; Map<Character, Integer> map = new HashMap<>();

    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(!map.containsKey(c)){
            map.put(c, i);
        }
        else{
            int len = i - map.get(c) - 1;
            max = Math.max(max, len);
        }
    }
    return max;
}

}

Time Complexity:

The time complexity of the above solution is O(n) where n is the length of the string.

Space Complexity:

The space complexity of the above solution is O(n) where n is the length of the string. The hashmap can store all n characters of the string.

1