We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Substring Between Two Equal Characters

Number: 1746

Difficulty: Easy

Paid? No

Companies: Apple

Problem Description

Given a string s, determine the length of the longest substring that appears between two identical characters (excluding the two characters). If no such substring exists because no character repeats, return -1.

Key Insights

  • Use a data structure (hash table or dictionary) to record the first occurrence of each character.
  • As you iterate through the string, whenever you encounter a character that has appeared before, calculate the current substring length (current index - first occurrence index - 1).
  • Update the maximum substring length if the current calculation exceeds the previous maximum.
  • If no character appears twice, return -1.

Space and Time Complexity

Time Complexity: O(n) – where n is the length of the string; each character is processed once. Space Complexity: O(1) – only a fixed size (26 letters) hash table is used regardless of the string size.

Solution

The approach involves scanning the input string and storing the index of the first occurrence of each character in a hash table. For every character seen later that has already been encountered, compute the length of the substring between its first occurrence and the current index (subtracting 1 to exclude the endpoints). Keep track of the maximum substring length found. If no such pair exists, return -1. This method leverages the properties of hash tables for constant time lookups and updates.

Code Solutions

# Python solution with line-by-line comments

def max_length_between_equal_characters(s):
    # Create a dictionary to store the first occurrence of each character.
    first_occurrence = {}
    # Variable to keep track of the maximum substring length found.
    max_length = -1
    
    # Iterate through each character in the string along with its index.
    for index, char in enumerate(s):
        # If the character is seen for the first time, record it.
        if char not in first_occurrence:
            first_occurrence[char] = index
        else:
            # Calculate the length of substring between the first occurrence and current index.
            current_length = index - first_occurrence[char] - 1
            # Update max_length if current_length is greater.
            max_length = max(max_length, current_length)
            
    # Return the maximum length found or -1 if not found.
    return max_length

# Example usage:
print(max_length_between_equal_characters("abca"))  # Expected output: 2
← Back to All Questions