LeetCode 2399: Check Distances Between Same Letters (First-Index Tracking)
LeetCode 2399StringIndexingToday we solve LeetCode 2399 - Check Distances Between Same Letters.
Source: https://leetcode.com/problems/check-distances-between-same-letters/
English
Problem Summary
Given a string s where each letter appears either once or twice, and an array distance of size 26, verify whether for every letter that appears twice, the number of characters between its two occurrences equals distance[letter].
Key Insight
When we see a letter for the first time, store its index. When we see it again, the required gap is simply i - firstIndex - 1. Compare it with the expected value in distance. Any mismatch means the answer is false.
Algorithm
- Prepare an array first of length 26, initialized to -1.
- Scan each character s[i].
- If first time seen: store index in first[idx].
- Else compute gap = i - first[idx] - 1 and compare with distance[idx].
- Return false immediately on mismatch; otherwise return true after scan.
Complexity Analysis
Let n be length of s.
Time: O(n).
Space: O(1) (fixed-size arrays).
Common Pitfalls
- Using i - firstIndex instead of i - firstIndex - 1 (off-by-one).
- Forgetting to initialize first-occurrence storage to -1.
- Trying to count characters manually between two positions, which is unnecessary.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean checkDistances(String s, int[] distance) {
int[] first = new int[26];
java.util.Arrays.fill(first, -1);
for (int i = 0; i < s.length(); i++) {
int idx = s.charAt(i) - 'a';
if (first[idx] == -1) {
first[idx] = i;
} else {
int gap = i - first[idx] - 1;
if (gap != distance[idx]) {
return false;
}
}
}
return true;
}
}func checkDistances(s string, distance []int) bool {
first := make([]int, 26)
for i := 0; i < 26; i++ {
first[i] = -1
}
for i := 0; i < len(s); i++ {
idx := int(s[i] - 'a')
if first[idx] == -1 {
first[idx] = i
} else {
gap := i - first[idx] - 1
if gap != distance[idx] {
return false
}
}
}
return true
}class Solution {
public:
bool checkDistances(string s, vector<int>& distance) {
vector<int> first(26, -1);
for (int i = 0; i < (int)s.size(); ++i) {
int idx = s[i] - 'a';
if (first[idx] == -1) {
first[idx] = i;
} else {
int gap = i - first[idx] - 1;
if (gap != distance[idx]) {
return false;
}
}
}
return true;
}
};class Solution:
def checkDistances(self, s: str, distance: List[int]) -> bool:
first = [-1] * 26
for i, ch in enumerate(s):
idx = ord(ch) - ord('a')
if first[idx] == -1:
first[idx] = i
else:
gap = i - first[idx] - 1
if gap != distance[idx]:
return False
return Truevar checkDistances = function(s, distance) {
const first = new Array(26).fill(-1);
for (let i = 0; i < s.length; i++) {
const idx = s.charCodeAt(i) - 97;
if (first[idx] === -1) {
first[idx] = i;
} else {
const gap = i - first[idx] - 1;
if (gap !== distance[idx]) {
return false;
}
}
}
return true;
};中文
题目概述
给定字符串 s（每个字母出现 1 次或 2 次）以及长度为 26 的数组 distance，需要判断：对每个出现两次的字母，这两次出现之间的字符数是否恰好等于 distance 对应值。
核心思路
首次遇到某个字母时记录下标；第二次遇到时直接用公式 i - firstIndex - 1 算中间字符数，并与 distance[idx] 对比。只要有一个不匹配，就可以立刻返回 false。
算法步骤
- 准备长度为 26 的数组 first，初始全为 -1。
- 遍历字符串 s 的每个位置 i。
- 若字母第一次出现，记录 first[idx] = i。
- 若字母第二次出现，计算 gap = i - first[idx] - 1 并与 distance[idx] 比较。
- 若遍历中从未出现不匹配，最终返回 true。
复杂度分析
设字符串长度为 n。
时间复杂度：O(n)。
空间复杂度：O(1)（固定 26 长度）。
常见陷阱
- 把间隔写成 i - firstIndex，少减了 1。
- 忘记把首下标数组初始化为 -1。
- 不必要地手动数区间字符，增加出错概率。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean checkDistances(String s, int[] distance) {
int[] first = new int[26];
java.util.Arrays.fill(first, -1);
for (int i = 0; i < s.length(); i++) {
int idx = s.charAt(i) - 'a';
if (first[idx] == -1) {
first[idx] = i;
} else {
int gap = i - first[idx] - 1;
if (gap != distance[idx]) {
return false;
}
}
}
return true;
}
}func checkDistances(s string, distance []int) bool {
first := make([]int, 26)
for i := 0; i < 26; i++ {
first[i] = -1
}
for i := 0; i < len(s); i++ {
idx := int(s[i] - 'a')
if first[idx] == -1 {
first[idx] = i
} else {
gap := i - first[idx] - 1
if gap != distance[idx] {
return false
}
}
}
return true
}class Solution {
public:
bool checkDistances(string s, vector<int>& distance) {
vector<int> first(26, -1);
for (int i = 0; i < (int)s.size(); ++i) {
int idx = s[i] - 'a';
if (first[idx] == -1) {
first[idx] = i;
} else {
int gap = i - first[idx] - 1;
if (gap != distance[idx]) {
return false;
}
}
}
return true;
}
};class Solution:
def checkDistances(self, s: str, distance: List[int]) -> bool:
first = [-1] * 26
for i, ch in enumerate(s):
idx = ord(ch) - ord('a')
if first[idx] == -1:
first[idx] = i
else:
gap = i - first[idx] - 1
if gap != distance[idx]:
return False
return Truevar checkDistances = function(s, distance) {
const first = new Array(26).fill(-1);
for (let i = 0; i < s.length; i++) {
const idx = s.charCodeAt(i) - 97;
if (first[idx] === -1) {
first[idx] = i;
} else {
const gap = i - first[idx] - 1;
if (gap !== distance[idx]) {
return false;
}
}
}
return true;
};
Comments