Largest Substring Between Two Equal Characters — Solution
Largest Substring Between Two Equal Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Largest Substring Between Two Equal Characters is an easy coding problem on strings and hash table, asked in Amazon, TCS and Infosys interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table
- Asked at: Amazon, TCS, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, return the length of the longest substring that sits strictly between two equal characters, not counting those two characters themselves.
If no character repeats, return -1.
Example 1
Input: s = "codekairo"
Output: 6
Explanation: The only repeated character is o, at indices 1 and 8, enclosing "dekair".
Example 2
Input: s = "abca"
Output: 2
Explanation: The two a's enclose "bc".
Example 3
Input: s = "cbzxy"
Output: -1
Explanation: Nothing repeats.
Constraints
1 <= s.length <= 300s consists of lowercase English letters.
Hints for Largest Substring Between Two Equal Characters
Hint 1
For a fixed character, the widest gap always uses its first and last occurrence.
Hint 2
So record the first index of each character and, on every later sighting, measure back to it.
Hint 3
The answer counts the characters strictly inside, which is
last - first - 1.
How to solve Largest Substring Between Two Equal Characters
The gap for a character is maximised by its earliest and latest occurrence, so storing each character's first index and measuring from it on every repeat covers every candidate.
Approach
- Sweep
iovers, keeping a map from character to its first index. - On a character already in the map, the candidate length is
i - first[c] - 1. - Keep the maximum, starting from
-1so a string with no repeat answers correctly.
Why it works
For a character c appearing at indices i1 < i2 < … < ik, every pair gives ij - ii - 1, which is largest when ii is the first and ij the last. Measuring every occurrence against the stored first index therefore reaches that maximum.
Complexity
- Time —
O(n) - Space —
O(1) — at most 26 entries
Pitfalls
- Overwriting the stored index on each sighting measures against the previous occurrence, not the first.
- Returning
last - firstcounts the two bookend characters, which the statement excludes.
Reference solution
Python
def maxLengthBetweenEqualCharacters(s: str) -> int:
first = {}
best = -1
for i, c in enumerate(s):
if c not in first:
first[c] = i
elif i - first[c] - 1 > best:
best = i - first[c] - 1
return bestJava
public static int maxLengthBetweenEqualCharacters(String s) {
int[] first = new int[26];
Arrays.fill(first, -1);
int best = -1;
for (int i = 0; i < s.length(); i++) {
int c = s.charAt(i) - 'a';
if (first[c] < 0) first[c] = i;
else if (i - first[c] - 1 > best) best = i - first[c] - 1;
}
return best;
}C++
int maxLengthBetweenEqualCharacters(string s) {
vector<int> first(26, -1);
int best = -1;
for (int i = 0; i < (int) s.size(); i++) {
int c = s[i] - 'a';
if (first[c] < 0) first[c] = i;
else if (i - first[c] - 1 > best) best = i - first[c] - 1;
}
return best;
}JavaScript
var maxLengthBetweenEqualCharacters = function(s) {
var first = {}, best = -1;
for (var i = 0; i < s.length; i++) {
var c = s.charAt(i);
if (first[c] === undefined) first[c] = i;
else if (i - first[c] - 1 > best) best = i - first[c] - 1;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets