# Largest Substring Between Two Equal Characters
**Difficulty:** EASY
[External](https://leetcode.com/problems/largest-substring-between-two-equal-characters)
Canonical: https://scaleengineer.com/dsa/problems/largest-substring-between-two-equal-characters
**Data structures:** Hash Table, String
---
## 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.

**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
## 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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Single Pass with First Occurrence Tracking
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int maxLengthBetweenEqualCharacters(String s) {
        int[] firstIndex = new int[26];
        Arrays.fill(firstIndex, -1);
        int maxLength = -1;

        for (int i = 0; i < s.length(); i++) {
            int charIndex = s.charAt(i) - 'a';
            if (firstIndex[charIndex] == -1) {
                firstIndex[charIndex] = i;
            } else {
                maxLength = Math.max(maxLength, i - firstIndex[charIndex] - 1);
            }
        }
        return maxLength;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxLengthBetweenEqualCharacters(string s) {
    vector<int> d(26, -1);
    int ans = -1;
    for (int i = 0; i < s.size(); ++i) {
      int j = s[i] - 'a';
      if (d[j] == -1) {
        d[j] = i;
      } else {
        ans = max(ans, i - d[j] - 1);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```