Scale Engineer

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 TableString

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.

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

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.

Solutions

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 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 →

Next problem