algoadvance

Leetcode 1624. Largest Substring Between Two Equal Characters

Problem Statement

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

Example

  1. Input: s = "aa" Output: 0 Explanation: The only substring between the two ‘a’s is an empty string.

  2. Input: s = "abca" Output: 2 Explanation: The substring between the two ‘a’s is “bc”.

  3. Input: s = "cbzxy" Output: -1 Explanation: There are no two identical characters, hence no valid substring exists.

  4. Input: s = "cabbac" Output: 4 Explanation: The substring between the two ‘c’s is “abba”.

Clarifying Questions

  1. Are all characters in s lowercase English letters?
  2. Is there a length constraint on the input string s?

Strategy

  1. Initialize a map to store the first occurrence index of each character.
  2. Traverse the string s and for each character, do the following:
    • Check if the character is already in the map:
      • If yes: Calculate the length of the substring between the current position and the stored index of the first occurrence of the character.
      • Update the maximum length if the calculated length is greater than the current maximum length.
      • Do not update the map since we are interested in the first and last occurrence.
    • If no: Store the index of the character in the map.
  3. Finally, return the maximum length or -1 if no valid substring is found.

Code

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int maxLengthBetweenEqualCharacters(string s) {
    unordered_map<char, int> firstIndex;
    int maxLength = -1;
    
    for (int i = 0; i < s.length(); i++) {
        if (firstIndex.find(s[i]) != firstIndex.end()) {
            int currentLength = i - firstIndex[s[i]] - 1;
            maxLength = max(maxLength, currentLength);
        } else {
            firstIndex[s[i]] = i;
        }
    }
    
    return maxLength;
}

// Sample usage
int main() {
    string s = "cabbac";
    cout << maxLengthBetweenEqualCharacters(s) << endl;  // Output: 4
    return 0;
}

Time Complexity

The time complexity for this solution is O(n) where n is the length of the string s. This is because we only traverse the string once, and each operation inside the loop (hash map operations) can be done in constant time on average.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI