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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Substring Between Two Equal Characters

Difficulty: Easy

Problem Description

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1. A substring is a contiguous sequence of characters within a string.

Key Insights

  • The problem requires finding pairs of equal characters in the string.
  • The length of the substring between two equal characters is calculated using their indices.
  • We can utilize a hash table (dictionary) to store the first occurrence of each character.
  • The goal is to find the maximum length of substrings formed between pairs of equal characters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. We traverse the string once. Space Complexity: O(1), since we only store a fixed number of characters in the hash table (26 lowercase letters).

Solution

To solve the problem, we will use a hash table to keep track of the first index where each character occurs as we iterate through the string. For each character, we will check if it has been seen before. If it has, we calculate the length of the substring between the two equal characters and update our maximum length if this length is greater than the previously recorded maximum. If no characters repeat, we will return -1.

Code Solutions

def longestSubstringBetweenEqualCharacters(s: str) -> int:
    index_map = {}  # To store the first index of each character
    max_length = -1  # To track the maximum length found

    for i, char in enumerate(s):
        if char in index_map:
            # Calculate the length of the substring between the two equal characters
            length = i - index_map[char] - 1
            max_length = max(max_length, length)
        else:
            index_map[char] = i  # Store the index of the first occurrence

    return max_length
← Back to All Questions