Largest Substring Between Two Equal Characters

Largest Substring Between Two Equal Characters - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abaca"

› Output: 3

💡 Note: The longest substring between two equal characters is "bac" between the first 'a' (index 0) and last 'a' (index 4), which has length 3.

Example 2 — Multiple Pairs

$ Input: s = "aa"

› Output: 0

💡 Note: The two 'a' characters are adjacent with no characters between them, so the substring length is 0.

Example 3 — No Equal Characters

$ Input: s = "cbzxy"

› Output: -1

💡 Note: No two equal characters exist in the string, so return -1.

Constraints

1 ≤ s.length ≤ 300
s contains only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with characters at different positions

Find Equal Pairs

Identify characters that appear multiple times

Calculate Lengths

Measure substring length between equal characters

Key Takeaway

🎯 Key Insight: The maximum substring length for any character is always between its first and last occurrence in the string

Asked in

a Amazon 12 G Google 8

The key insight is that for each character, the maximum substring length is between its first and last occurrence. The optimal approach uses a single-pass hash map to track first occurrences and calculate lengths on the fly. Time: O(n), Space: O(k) where k is the number of unique characters.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Track First and Last Positions	O(n)	O(k)	Use hash map to store first and last occurrence of each character
Brute Force - Check All Pairs	O(n²)	O(1)	Check every pair of characters to find matching ones with maximum distance
Single Pass with Hash Map	O(n)	O(k)	Track first occurrence and calculate maximum length in a single pass

Hash Map - Track First and Last Positions — Algorithm Steps

Step 1: First pass - record first occurrence of each character
Step 2: Second pass - for each character, calculate distance from first occurrence
Step 3: Track maximum distance found

Visualization

Tap to expand

Step-by-Step Walkthrough

First Pass

Record first occurrence of each character

Second Pass

Calculate distance from first occurrence

Maximum

Track the largest distance found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int solution(char* s) {
    int firstOccurrence[256];
    bool seen[256] = {false};
    int maxLength = -1;
    int n = strlen(s);
    
    // First pass: record first occurrence
    for (int i = 0; i < n; i++) {
        unsigned char ch = s[i];
        if (!seen[ch]) {
            firstOccurrence[ch] = i;
            seen[ch] = true;
        }
    }
    
    // Second pass: calculate max length
    for (int i = 0; i < n; i++) {
        unsigned char ch = s[i];
        if (seen[ch]) {
            int length = i - firstOccurrence[ch] - 1;
            if (length > maxLength) {
                maxLength = length;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through string of length n

✓ Linear Growth

Space Complexity

O(k)

Hash map stores at most k unique characters, where k ≤ 26 for lowercase letters

✓ Linear Space

18.2K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Track First and Last Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler