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).
1#include <iostream>
2#include <unordered_map>
3using namespace std;
4
5int maxLengthBetweenEqualCharacters(string s) {
6 unordered_map<char, int> firstOccurrence;
7 int maxLen = -1;
8 for (int i = 0; i < s.length(); i++) {
9 if (firstOccurrence.count(s[i]) == 0) {
10 firstOccurrence[s[i]] = i;
11 } else {
12 maxLen = max(maxLen, i - firstOccurrence[s[i]] - 1);
13 }
14 }
15 return maxLen;
16}
17
18int main() {
19 string s = "abca";
20 int result = maxLengthBetweenEqualCharacters(s);
21 cout << result << endl;
22 return 0;
23}Using an unordered map, this C++ solution keeps track of the first position of each character in the string. It calculates the maximum length for any repeated character throughout the string.
In this C code, two arrays are used for first and last occurrence tracking. The two-pass approach ensures we retain needed indices to measure lengths effectively.