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 <stdio.h>
2#include <string.h>
3#define MAX_CHAR 256
4
5int maxLengthBetweenEqualCharacters(char * s) {
6 int firstOccurrence[MAX_CHAR];
7 memset(firstOccurrence, -1, sizeof(firstOccurrence));
8 int maxLen = -1;
9 for (int i = 0; s[i] != '\0'; i++) {
10 char c = s[i];
11 if (firstOccurrence[c] == -1) {
12 firstOccurrence[c] = i;
13 } else {
14 int len = i - firstOccurrence[c] - 1;
15 if (len > maxLen) {
16 maxLen = len;
17 }
18 }
19 }
20 return maxLen;
21}
22
23int main() {
24 char s[] = "abca";
25 int result = maxLengthBetweenEqualCharacters(s);
26 printf("%d\n", result);
27 return 0;
28}This code initializes an array to track the first occurrence of each character. It iterates through the string, updating the maximum length between identical characters by checking current indices against their recorded first occurrence.
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).
1using System.Collections.Generic;
public class Solution {
public int MaxLengthBetweenEqualCharacters(string s) {
Dictionary<char, int> firstOccurrence = new Dictionary<char, int>();
Dictionary<char, int> lastOccurrence = new Dictionary<char, int>();
int maxLen = -1;
for (int i = 0; i < s.Length; i++) {
if (!firstOccurrence.ContainsKey(s[i])) {
firstOccurrence[s[i]] = i;
}
lastOccurrence[s[i]] = i;
}
foreach (var pair in firstOccurrence) {
maxLen = Math.Max(maxLen, lastOccurrence[pair.Key] - pair.Value - 1);
}
return maxLen;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MaxLengthBetweenEqualCharacters("abca"));
}
}This C# code leverages two-pass logic with dictionaries for keeping track of where characters first and last appear, which helps derive substring lengths aptly.