Largest Substring Between Two Equal Characters solution and explanation
9 more videos on this problem
Largest Substring Between Two Equal Characters - Leetcode 1624 - PythonNeetCodeIO · 7:05 · 11K views
Largest Substring Between Two Equal Characters | 3 Ways | C++ | JAVA | Leetcode 1624codestorywithMIK · 13:52 · 4K views
Leetcode 1624. Largest Substring Between Two Equal CharactersFraz · 6:39 · 2K views
largest substring between two equal characters leetcode | leetcode 1624Naresh Gupta · 8:58 · 1K views
LeetCode 1624. Largest Substring Between Two Equal Characters - Interview Prep Ep 101Fisher Coder · 6:10 · 897 views
Leetcode | 1624. Largest Substring Between Two Equal Characters | Easy | Java SolutionDeveloper Docs · 6:57 · 586 views
1624. Largest Substring Between Two Equal Characters (Leetcode Easy)Programming Live with Larry · 2:54 · 373 views
Daily Leetcode #1370: Dec 31, 2023 - 1624. Largest Substring Between Two Equal CharactersProgramming Live with Larry · 9:17 · 277 views
Largest Substring Between Two Equal Characters - LeetCode #1624 - Python, JavaScript, Java and C++CodingNinja · 8:17 · 214 views
Largest Substring Between Two Equal Characters (leetcode daily challenge) 1624Gupta_vibes · 5:22 · 175 views
The 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 <= 300scontains only lowercase English letters.
Approach overview
Problem Overview: You receive a string s. The goal is to find the length of the largest substring that lies strictly between two equal characters. Only the characters between the pair count. If no such pair exists, return -1.
Approach 1: Hash Map (O(n) time, O(1) space)
Track the first occurrence of every character while scanning the string from left to right. Use a hash table that maps each character to its earliest index. When you encounter the same character again at index i, compute the substring length as i - firstIndex - 1. Update the maximum length if this value is larger. Because the alphabet size is limited (typically lowercase English letters), the extra space remains constant.
The key insight: the longest substring for a character always occurs between its first appearance and the farthest later occurrence. Storing only the first index guarantees the maximum gap when the character appears again.
Approach 2: Two-Pass Approach (O(n) time, O(1) space)
This method separates discovery of character positions from computing distances. In the first pass, record the first index where each character appears. In the second pass, update the last index seen for each character and compute the distance between the first and current position. The substring length is again last - first - 1. This approach still runs in linear time and uses constant extra memory due to the small alphabet.
The logic relies entirely on simple array or map lookups and sequential scans of the string. No nested loops are required, which keeps the solution efficient even for large inputs.
Recommended for interviews: The hash map approach is the expected solution. It shows you recognize the pattern of storing first occurrences and performing constant-time lookups during a single pass. Interviewers often accept the two-pass version as well, but the single-pass hash table solution demonstrates stronger algorithmic instinct and cleaner implementation.
Approach 1: Hash Map Approach
This approach uses a hash map to store the first and last occurrence of each character as you traverse the string. For each character, calculate the distance between its occurrences and keep track of the maximum distance found. This efficiently provides the length of the longest substring between two identical characters.
def maxLengthBetweenEqualCharacters(s: str) -> int:
first_occurrence = {}
max_len = -1
for i, char in enumerate(s):
if char not in first_occurrence:
first_occurrence[char] = i
else:
max_len = max(max_len, i - first_occurrence[char] - 1)
return max_len
s = "abca"
result = maxLengthBetweenEqualCharacters(s)
print(result)import java.util.HashMap;
public class MaxLengthBetweenEqualCharacters {
public int maxLengthBetweenEqualCharacters(String s) {
HashMap<Character, Integer> firstOccurrence = new HashMap<>();
int maxLen = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!firstOccurrence.containsKey(c)) {
firstOccurrence.put(c, i);
} else {
maxLen = Math.max(maxLen, i - firstOccurrence.get(c) - 1);
}
}
return maxLen;
}
public static void main(String[] args) {
MaxLengthBetweenEqualCharacters solution = new MaxLengthBetweenEqualCharacters();
System.out.println(solution.maxLengthBetweenEqualCharacters("abca"));
}
}#include <iostream>
#include <unordered_map>
using namespace std;
int maxLengthBetweenEqualCharacters(string s) {
unordered_map<char, int> firstOccurrence;
int maxLen = -1;
for (int i = 0; i < s.length(); i++) {
if (firstOccurrence.count(s[i]) == 0) {
firstOccurrence[s[i]] = i;
} else {
maxLen = max(maxLen, i - firstOccurrence[s[i]] - 1);
}
}
return maxLen;
}
int main() {
string s = "abca";
int result = maxLengthBetweenEqualCharacters(s);
cout << result << endl;
return 0;
}var maxLengthBetweenEqualCharacters = function(s) {
let firstOccurrence = {};
let maxLen = -1;
for (let i = 0; i < s.length; i++) {
if (!(s[i] in firstOccurrence)) {
firstOccurrence[s[i]] = i;
} else {
maxLen = Math.max(maxLen, i - firstOccurrence[s[i]] - 1);
}
}
return maxLen;
};
console.log(maxLengthBetweenEqualCharacters('abca'));#include <stdio.h>
#include <string.h>
#define MAX_CHAR 256
int maxLengthBetweenEqualCharacters(char * s) {
int firstOccurrence[MAX_CHAR];
memset(firstOccurrence, -1, sizeof(firstOccurrence));
int maxLen = -1;
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (firstOccurrence[c] == -1) {
firstOccurrence[c] = i;
} else {
int len = i - firstOccurrence[c] - 1;
if (len > maxLen) {
maxLen = len;
}
}
}
return maxLen;
}
int main() {
char s[] = "abca";
int result = maxLengthBetweenEqualCharacters(s);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxLengthBetweenEqualCharacters(string s) {
Dictionary<char, int> firstOccurrence = new Dictionary<char, int>();
int maxLen = -1;
for (int i = 0; i < s.Length; i++) {
if (!firstOccurrence.ContainsKey(s[i])) {
firstOccurrence[s[i]] = i;
} else {
maxLen = Math.Max(maxLen, i - firstOccurrence[s[i]] - 1);
}
}
return maxLen;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MaxLengthBetweenEqualCharacters("abca"));
}
}This Python function also employs a dictionary to store character first occurrences. It computes the longest substring by the difference of current and first indices for repeated characters, minus one.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Two-Pass Approach
This approach involves two pass-throughs of the string. The first pass records each character's first occurrence, while the second calculates potential maximum lengths using each character's last occurrence.
def maxLengthBetweenEqualCharacters(s: str) -> int:
first_occurrence = {}
last_occurrence = {}
max_len = -1
for i, char in enumerate(s):
if char not in first_occurrence:
first_occurrence[char] = i
last_occurrence[char] = i
for char in first_occurrence:
max_len = max(max_len, last_occurrence[char] - first_occurrence[char] - 1)
return max_len
s = "abca"
result = maxLengthBetweenEqualCharacters(s)
print(result)import java.util.HashMap;
public class MaxLengthBetweenEqualCharacters {
public int maxLengthBetweenEqualCharacters(String s) {
HashMap<Character, Integer> firstOccurrence = new HashMap<>();
HashMap<Character, Integer> lastOccurrence = new HashMap<>();
int maxLen = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!firstOccurrence.containsKey(c)) {
firstOccurrence.put(c, i);
}
lastOccurrence.put(c, i);
}
for (char c : firstOccurrence.keySet()) {
maxLen = Math.max(maxLen, lastOccurrence.get(c) - firstOccurrence.get(c) - 1);
}
return maxLen;
}
public static void main(String[] args) {
MaxLengthBetweenEqualCharacters solution = new MaxLengthBetweenEqualCharacters();
System.out.println(solution.maxLengthBetweenEqualCharacters("abca"));
}
}#include <iostream>
#include <unordered_map>
using namespace std;
int maxLengthBetweenEqualCharacters(string s) {
unordered_map<char, int> firstOccurrence;
unordered_map<char, int> lastOccurrence;
int maxLen = -1;
for (int i = 0; i < s.length(); i++) {
if (firstOccurrence.find(s[i]) == firstOccurrence.end()) {
firstOccurrence[s[i]] = i;
}
lastOccurrence[s[i]] = i;
}
for (auto pair : firstOccurrence) {
maxLen = max(maxLen, lastOccurrence[pair.first] - pair.second - 1);
}
return maxLen;
}
int main() {
string s = "abca";
int result = maxLengthBetweenEqualCharacters(s);
cout << result << endl;
return 0;
}var maxLengthBetweenEqualCharacters = function(s) {
let firstOccurrence = {};
let lastOccurrence = {};
let maxLen = -1;
for (let i = 0; i < s.length; i++) {
if (!(s[i] in firstOccurrence)) {
firstOccurrence[s[i]] = i;
}
lastOccurrence[s[i]] = i;
}
for (let char in firstOccurrence) {
maxLen = Math.max(maxLen, lastOccurrence[char] - firstOccurrence[char] - 1);
}
return maxLen;
};
console.log(maxLengthBetweenEqualCharacters('abca'));#include <stdio.h>
#include <string.h>
#define MAX_CHAR 256
int maxLengthBetweenEqualCharacters(char * s) {
int firstOccurrence[MAX_CHAR];
int lastOccurrence[MAX_CHAR];
memset(firstOccurrence, -1, sizeof(firstOccurrence));
int maxLen = -1;
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (firstOccurrence[c] == -1) {
firstOccurrence[c] = i;
}
lastOccurrence[c] = i;
}
for (int i = 0; i < MAX_CHAR; i++) {
if (firstOccurrence[i] != -1) {
int len = lastOccurrence[i] - firstOccurrence[i] - 1;
if (len > maxLen) {
maxLen = len;
}
}
}
return maxLen;
}
int main() {
char s[] = "abca";
int result = maxLengthBetweenEqualCharacters(s);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxLengthBetweenEqualCharacters(string s) {
Dictionary<char, int> firstOccurrence = new Dictionary<char, int>();
Dictionary<char, int> lastOccurrence = new Dictionary<char, int>();
int maxLen = -1;
for (int i = 0; i < s.Length; i++) {
if (!firstOccurrence.ContainsKey(s[i])) {
firstOccurrence[s[i]] = i;
}
lastOccurrence[s[i]] = i;
}
foreach (var pair in firstOccurrence) {
maxLen = Math.Max(maxLen, lastOccurrence[pair.Key] - pair.Value - 1);
}
return maxLen;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MaxLengthBetweenEqualCharacters("abca"));
}
}Python solution involves using two dictionaries to record initial and final character appearances, then determining the longest valid substrings calculated from these indices.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Default Approach
function maxLengthBetweenEqualCharacters(s: string): number {
const n = s.length;
const pos = new Array(26).fill(-1);
let res = -1;
for (let i = 0; i < n; i++) {
const j = s[i].charCodeAt(0) - 'a'.charCodeAt(0);
if (pos[j] === -1) {
pos[j] = i;
} else {
res = Math.max(res, i - pos[j] - 1);
}
}
return res;
}func maxLengthBetweenEqualCharacters(s string) int {
d := make([]int, 26)
for i := range d {
d[i] = -1
}
ans := -1
for i, c := range s {
c -= 'a'
if d[c] == -1 {
d[c] = i
} else {
ans = max(ans, i-d[c]-1)
}
}
return ans
}impl Solution {
pub fn max_length_between_equal_characters(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut pos = [-1; 26];
let mut res = -1;
for i in 0..n {
let j = (s[i] - b'a') as usize;
let i = i as i32;
if pos[j] == -1 {
pos[j] = i;
} else {
res = res.max(i - pos[j] - 1);
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Hash Map Approach | Time Complexity: O(n). |
| Two-Pass Approach | Time Complexity: O(n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map | O(n) | O(1) | Best general solution. Single pass with constant-time lookups. |
| Two-Pass Approach | O(n) | O(1) | Useful when separating position tracking and distance calculation improves readability. |
Frequently asked questions
Is Largest Substring Between Two Equal Characters easy or hard?
Largest Substring Between Two Equal Characters is classified as an Easy problem. The challenge mainly involves understanding how to track the first occurrence of characters and compute the distance efficiently using a hash table.
Largest Substring Between Two Equal Characters Python/Java solution
Both Python and Java implementations follow the same idea: track the first index of each character and update the maximum substring length when the character repeats. The logic uses a dictionary in Python or a HashMap/array in Java and runs in O(n) time.
How to solve Largest Substring Between Two Equal Characters in O(n)?
Iterate through the string and store the first occurrence of each character in a hash map. When the same character appears again, calculate the substring length as currentIndex - firstIndex - 1. Track the maximum length during the scan. This single-pass strategy achieves O(n) time complexity.
What is the best approach for Largest Substring Between Two Equal Characters?
The hash map approach is the most efficient and commonly expected solution. Store the first index of each character while scanning the string. When the character appears again, compute the distance between the current index and the stored index minus one. This runs in O(n) time with O(1) space.
Is Largest Substring Between Two Equal Characters asked at Google/Amazon/Meta?
Problems involving string indexing, hash tables, and substring calculations frequently appear in interviews at companies like Amazon and Meta. While this exact problem may not always appear, the pattern of tracking first occurrences with a hash map is common in coding interviews.
What data structure is used in Largest Substring Between Two Equal Characters?
A hash table (or hash map) is the primary data structure used in the optimal solution. It stores the first index where each character appears, allowing constant-time lookups when the character appears again later in the string.
What is the time complexity of Largest Substring Between Two Equal Characters?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once, and hash table lookups are constant time. Space complexity is O(1) because the number of possible characters is limited.