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).
1import java.util.HashMap;
2
3public class MaxLengthBetweenEqualCharacters {
4 public int maxLengthBetweenEqualCharacters(String s) {
5 HashMap<Character, Integer> firstOccurrence = new HashMap<>();
6 int maxLen = -1;
7 for (int i = 0; i < s.length(); i++) {
8 char c = s.charAt(i);
9 if (!firstOccurrence.containsKey(c)) {
10 firstOccurrence.put(c, i);
11 } else {
12 maxLen = Math.max(maxLen, i - firstOccurrence.get(c) - 1);
13 }
14 }
15 return maxLen;
16 }
17
18 public static void main(String[] args) {
19 MaxLengthBetweenEqualCharacters solution = new MaxLengthBetweenEqualCharacters();
20 System.out.println(solution.maxLengthBetweenEqualCharacters("abca"));
21 }
22}In this Java solution, a HashMap is used to record each character's first occurrence, allowing the calculation of maximum length for valid substrings between identical characters.
This approach involves two pass-throughs of the string. The first pass records each character's first occurrence, while the second calculates potential maximum lengths using each character's last occurrence.
Time Complexity: O(n).
Space Complexity: O(1).
1#include <unordered_map>
using namespace std;
int maxLengthBetweenEqualCharacters(string s) {
unordered_map<char, int> firstOccurrence;
unordered_map<char, int> lastOccurrence;
int maxLen = -1;
for (int i = 0; i < s.length(); i++) {
if (firstOccurrence.find(s[i]) == firstOccurrence.end()) {
firstOccurrence[s[i]] = i;
}
lastOccurrence[s[i]] = i;
}
for (auto pair : firstOccurrence) {
maxLen = max(maxLen, lastOccurrence[pair.first] - pair.second - 1);
}
return maxLen;
}
int main() {
string s = "abca";
int result = maxLengthBetweenEqualCharacters(s);
cout << result << endl;
return 0;
}C++ implementation makes use of two unordered maps for recording first and last occurrences, facilitating the calculation of the longest substring length between identical characters.