algoadvance

Given a string s, find the length of the largest substring that occurs between two equal characters (inclusive of the characters). If there is no such substring, return -1.

Clarifying Questions

1. Input Constraints: What is the length range of the string s?
   • Typically constraints might be given, but for this problem let’s assume 1 <= s.length <= 10^4.
2. Character Set: What type of characters does the string s contain?
   • Assume the string contains only lowercase English letters.
3. Edge Cases: What should be returned if the string has no repeating characters?
   • Return -1 in such a case.
4. Inclusive/Exclusive: Should the characters themselves be included in the substring length?
   • For this problem, we will include the characters.

Strategy

1. Track First and Last Occurrences: Use a dictionary to record the first and last occurrence index of each character.
2. Calculate Maximum Length: Iterate through the dictionary and calculate the length of the substring for each character that appears more than once.
3. Return Result: Keep track of the maximum length found and return it. If no such substring exists, return -1.

Code

def maxLengthBetweenEqualCharacters(s: str) -> int:
    # Dictionary to store the first and last occurrence of each character
    char_indices = {}
    
    for i, char in enumerate(s):
        if char in char_indices:
            char_indices[char][1] = i  # Update the last occurrence
        else:
            char_indices[char] = [i, i]  # Initialize the first and last occurrence
    
    max_length = -1
    for first, last in char_indices.values():
        if last > first:
            max_length = max(max_length, last - first + 1)
    
    return max_length

# Example usage
print(maxLengthBetweenEqualCharacters("abcadda"))  # Output: 7
print(maxLengthBetweenEqualCharacters("abcda"))    # Output: 5
print(maxLengthBetweenEqualCharacters("abcdef"))   # Output: -1

Time Complexity

• Time Complexity: The algorithm runs in O(n) where n is the length of the string. This is because we scan through the string to build the dictionary of first and last occurrences, and then scan through the dictionary to find the maximum length.
• Space Complexity: The space complexity is O(1), as the dictionary will have at most 26 entries (one for each letter in the English alphabet). This makes it effectively constant space concerning the number of different lowercase English characters.

This approach ensures that we efficiently find the largest substring between two equal characters in linear time while maintaining linear space complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?