2399. Check Distances Between Same Letters
Description
You are given a 0-indexed string s
consisting of only lowercase English letters, where each letter in s
appears exactly twice. You are also given a 0-indexed integer array distance
of length 26
.
Each letter in the alphabet is numbered from 0
to 25
(i.e. 'a' -> 0
, 'b' -> 1
, 'c' -> 2
, ... , 'z' -> 25
).
In a well-spaced string, the number of letters between the two occurrences of the ith
letter is distance[i]
. If the ith
letter does not appear in s
, then distance[i]
can be ignored.
Return true
if s
is a well-spaced string, otherwise return false
.
Example 1:
Input: s = "abaccb", distance = [1,3,0,5,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: - 'a' appears at indices 0 and 2 so it satisfies distance[0] = 1. - 'b' appears at indices 1 and 5 so it satisfies distance[1] = 3. - 'c' appears at indices 3 and 4 so it satisfies distance[2] = 0. Note that distance[3] = 5, but since 'd' does not appear in s, it can be ignored. Return true because s is a well-spaced string.
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: - 'a' appears at indices 0 and 1 so there are zero letters between them. Because distance[0] = 1, s is not a well-spaced string.
Constraints:
2 <= s.length <= 52
s
consists only of lowercase English letters.- Each letter appears in
s
exactly twice. distance.length == 26
0 <= distance[i] <= 50
Solutions
Solution 1: Array or Hash Table
We can use a hash table $d$ to record the indices of each letter's occurrences. Then, traverse the hash table and check if the difference between the indices of each letter equals the corresponding value in the distance
array. If any discrepancy is found, return false
. If the traversal completes without discrepancies, return true
.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(|\Sigma|)$, where $\Sigma$ is the character set, which in this case is the set of lowercase letters.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|