Sponsored
Sponsored
This approach uses a hash map to store the first and last occurrence of each character as you traverse the string. For each character, calculate the distance between its occurrences and keep track of the maximum distance found. This efficiently provides the length of the longest substring between two identical characters.
Time Complexity: O(n) where n is the length of the string.
Space Complexity: O(1) since the hash map size is constant (fixed at 256 for all possible lowercase characters).
1var maxLengthBetweenEqualCharacters = function(s) {
2 let firstOccurrence = {};
3 let maxLen = -1;
4 for (let i = 0; i < s.length; i++) {
5 if (!(s[i] in firstOccurrence)) {
6 firstOccurrence[s[i]] = i;
7 } else {
8 maxLen = Math.max(maxLen, i - firstOccurrence[s[i]] - 1);
9 }
10 }
11 return maxLen;
12};
13
14console.log(maxLengthBetweenEqualCharacters('abca'));This JavaScript solution uses an object as a hashmap to store the indices of the first occurrence of each character, facilitating a calculation of the desired maximum length for the substring between identical characters.
Python solution involves using two dictionaries to record initial and final character appearances, then determining the longest valid substrings calculated from these indices.