Largest Substring Between Two Equal Characters

EASY

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.

Example 1:

Input: s = "aa"
Output: 0
Explanation: The optimal substring here is an empty substring between the two '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

Checkout 2 different approaches to solve Largest Substring Between Two Equal Characters. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

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.

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.

class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        int maxLength = -1;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    maxLength = Math.max(maxLength, j - i - 1);
                }
            }
        }
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1). The space used does not scale with the input string size; only a few variables are needed.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Largest Substring Between Two Equal Characters. Click on different languages to view the code.

class Solution {
public
  int maxLengthBetweenEqualCharacters(String s) {
    int[] d = new int[26];
    Arrays.fill(d, -1);
    int ans = -1;
    for (int i = 0; i < s.length(); ++i) {
      int j = s.charAt(i) - 'a';
      if (d[j] == -1) {
        d[j] = i;
      } else {
        ans = Math.max(ans, i - d[j] - 1);
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Largest Substring Between Two Equal Characters

Data Structures:

Hash TableString