Check Distances Between Same Letters — Problem & Solution
Check Distances Between Same Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Check Distances Between Same Letters is an easy coding problem on arrays, strings and hash table, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon
- 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
You are given a lowercase string s in which every letter that appears, appears exactly twice, and an integer array distance of length 26.
Letter i of the alphabet (a is 0, b is 1, …, z is 25) is well spaced if the number of characters strictly between its two occurrences equals distance[i]. Letters that do not appear in s are ignored.
Return true if every letter in s is well spaced, and false otherwise.
Example 1
Input: s = "bccb", distance = [0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: true
Explanation: The two `b`s have 2 characters between them and the two `c`s have 0, matching `distance[1] = 2` and `distance[2] = 0`.
Example 2
Input: s = "aa", distance = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: false
Explanation: The two `a`s are adjacent, with 0 characters between them, not 1.
Example 3
Input: s = "abcabc", distance = [2,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: false
Explanation: `a` and `b` each have 2 characters between their copies, but so does `c`, and `distance[2]` asks for 1.
Constraints
2 <= s.length <= 52s holds lowercase English letters; each letter in s appears exactly twicedistance.length == 260 <= distance[i] <= 50
Hints for Check Distances Between Same Letters
Hint 1
Record the index where each letter first appears.
Hint 2
When you meet a letter the second time at index
jafter first seeing it ati, the gap isj - i - 1.Hint 3
Compare that gap with
distance[letter]and stop at the first mismatch.
How to solve Check Distances Between Same Letters
One pass with a 26-slot table of first positions measures every letter's gap at its second occurrence.
Approach
- Fill
first[26]with -1. - For each index
j: letcbe the letter. Iffirst[c] == -1, set it toj; otherwise, ifj - first[c] - 1 != distance[c], return false. - Return true.
Why it works
Each letter appears exactly twice, so the second sighting closes its only gap, and j - i - 1 counts the characters strictly between positions i and j. Letters absent from s are never checked.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The distance counts characters between the copies: adjacent copies have distance 0, not 1.
- Only letters present in
sare checked;distanceentries for absent letters can be anything.
Reference solution
Python
from typing import List
def checkDistances(s: str, distance: List[int]) -> bool:
first = [-1] * 26
for j, ch in enumerate(s):
c = ord(ch) - 97
if first[c] == -1:
first[c] = j
elif j - first[c] - 1 != distance[c]:
return False
return TrueJava
public static boolean checkDistances(String s, int[] distance) {
int[] first = new int[26];
Arrays.fill(first, -1);
for (int j = 0; j < s.length(); j++) {
int c = s.charAt(j) - 'a';
if (first[c] == -1) first[c] = j;
else if (j - first[c] - 1 != distance[c]) return false;
}
return true;
}C++
bool checkDistances(string s, vector<int>& distance) {
vector<int> first(26, -1);
for (int j = 0; j < (int)s.size(); j++) {
int c = s[j] - 'a';
if (first[c] == -1) first[c] = j;
else if (j - first[c] - 1 != distance[c]) return false;
}
return true;
}JavaScript
var checkDistances = function(s, distance) {
var first = new Array(26).fill(-1);
for (var j = 0; j < s.length; j++) {
var c = s.charCodeAt(j) - 97;
if (first[c] === -1) first[c] = j;
else if (j - first[c] - 1 !== distance[c]) return false;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.