Largest Substring Between Two Equal Characters

Easy

#1492Time: O(n^2), where n is the length of the string `s`. The two nested loops lead to a quadratic number of character comparisons.Space: O(1). The space used does not scale with the input string size; only a few variables are needed.

Data structures

Hash Table String

Prompt

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.

Example 1:

'a's

Example 2:

Input: s = "abca"
Output: 2
Explanation: The optimal substring here is "bc".

Example 3:

Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.

Constraints:

1 <= s.length <= 300
s contains only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This straightforward approach uses nested loops to examine every possible pair of characters in the string. For each pair (i, j) with i < j, it checks if s.charAt(i) equals s.charAt(j). If they are equal, it calculates the length of the substring between them and updates a variable that keeps track of the maximum length found so far.

Algorithm

Initialize a variable maxLength to -1.
Use a nested loop structure. The outer loop iterates with index i from the start of the string to the end.
The inner loop iterates with index j from i + 1 to the end of the string.
Inside the inner loop, check if the character at index i is the same as the character at index j.
If they are equal, calculate the length of the substring between them, which is j - i - 1.
Update maxLength to be the maximum of its current value and the newly calculated length.
After the loops complete, return maxLength.

Walkthrough

The algorithm begins by initializing a variable, maxLength, to -1. This default value is returned if no character appears more than once. We then iterate through the string with a pair of nested loops. The outer loop picks the first character of a potential pair, and the inner loop picks the second character. If the two characters are identical, we've found a valid pair. The length of the substring between them is the difference in their indices minus one (j - i - 1). We compare this length with our current maxLength and update it if the new length is greater. This process continues until all possible pairs have been checked.

1class Solution {2    public int maxLengthBetweenEqualCharacters(String s) {3        int maxLength = -1;4        int n = s.length();5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                if (s.charAt(i) == s.charAt(j)) {8                    maxLength = Math.max(maxLength, j - i - 1);9                }10            }11        }12        return maxLength;13    }14}

Complexity

Time

O(n^2), where n is the length of the string `s`. The two nested loops lead to a quadratic number of character comparisons.

Space

O(1). The space used does not scale with the input string size; only a few variables are needed.

Trade-offs

Pros

It's simple to understand and implement.
It doesn't require any extra space apart from a few variables.

Cons

This approach is inefficient for large strings due to its O(n^2) time complexity.
It performs many redundant comparisons.

This optimized approach avoids the nested loops by making a single pass through the string. It uses an auxiliary array (or a hash map) to keep track of the first index at which each character appears. When we encounter a character again, we can immediately calculate the length of the substring between its current position and its first recorded position. By always using the first occurrence, we ensure that we are calculating the maximum possible substring length for that character.

Algorithm

Initialize maxLength to -1.
Create an integer array firstIndex of size 26 (for 'a' through 'z') and initialize all its values to -1.
Iterate through the input string s with index i from 0 to s.length() - 1.
For each character c at index i, calculate its corresponding index in the array: charIndex = c - 'a'.
Check if firstIndex[charIndex] is -1.
- If it is, this is the first time we've seen this character. Store its index: firstIndex[charIndex] = i.
- If it's not -1, the character has appeared before. Calculate the distance from its first appearance: i - firstIndex[charIndex] - 1. Update maxLength with the maximum of its current value and this new distance.
After the loop, return maxLength.

Walkthrough

We can significantly improve performance by realizing that the longest substring for any given character will be between its first and last occurrences. This approach finds this by iterating through the string just once. We use an integer array firstIndex of size 26, where each index corresponds to a letter of the alphabet. We initialize this array with -1s to signify that no character has been seen yet.

As we iterate through the string s, for each character c, we check our firstIndex array. If the entry for c is still -1, it's the first time we're encountering it, so we store the current index i in firstIndex[c - 'a']. If the entry is not -1, it means we've seen this character before at the index stored in the array. We then calculate the length of the substring between the current index and the first index (i - firstIndex[c - 'a'] - 1) and update our maxLength if this new length is greater. This single pass is sufficient to find the overall maximum length.

1import java.util.Arrays;2 3class Solution {4    public int maxLengthBetweenEqualCharacters(String s) {5        int[] firstIndex = new int[26];6        Arrays.fill(firstIndex, -1);7        int maxLength = -1;8 9        for (int i = 0; i < s.length(); i++) {10            int charIndex = s.charAt(i) - 'a';11            if (firstIndex[charIndex] == -1) {12                firstIndex[charIndex] = i;13            } else {14                maxLength = Math.max(maxLength, i - firstIndex[charIndex] - 1);15            }16        }17        return maxLength;18    }19}

Complexity

Time

O(n), where n is the length of the string `s`. We only need to iterate through the string once.

Space

O(1). The space required is for an array of size 26, which is constant and does not depend on the length of the input string.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Optimal solution for this problem.
Simple to implement using an array as a direct-access table.

Cons

Requires a small, constant amount of extra space for the tracking array.

Solutions

Solution

1class Solution {2public3  int maxLengthBetweenEqualCharacters(String s) {4    int[] d = new int[26];5    Arrays.fill(d, -1);6    int ans = -1;7    for (int i = 0; i < s.length(); ++i) {8      int j = s.charAt(i) - 'a';9      if (d[j] == -1) {10        d[j] = i;11      } else {12        ans = Math.max(ans, i - d[j] - 1);13      }14    }15    return ans;16  }17}

1class Solution {2public:3  int maxLengthBetweenEqualCharacters(string s) {4    vector<int> d(26, -1);5    int ans = -1;6    for (int i = 0; i < s.size(); ++i) {7      int j = s[i] - 'a';8      if (d[j] == -1) {9        d[j] = i;10      } else {11        ans = max(ans, i - d[j] - 1);12      }13    }14    return ans;15  }16};

1class Solution:2    def maxLengthBetweenEqualCharacters(self, s: str) -> int: d = {} ans = - 1 for i, c in enumerate(s): if c in d: ans = max(ans, i - d[c] - 1) else: d[c] = i return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem