#2399

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Check Distances Between Same Letters

Verify if each pair of identical letters in a string has the exact number of letters between them as specified in a distance array.

array hash table string

Problem Statement

You are given a string s consisting of only lowercase English letters, where each letter appears exactly twice, and an integer array distance of length 26. Each letter corresponds to an index from 0 to 25 ('a' -> 0, 'b' -> 1, ..., 'z' -> 25). Your task is to determine if the string is well-spaced according to distance, meaning the number of letters between two identical letters matches distance[i] for the corresponding letter.

For each letter in s, if it occurs at positions i and j, the number of letters between them should equal distance[letterIndex]. If a letter does not appear in s, its distance can be ignored. Return true if all letters meet their required spacing; otherwise, return false.

Examples

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

'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

'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

Solution Approach

Initialize tracking array

Create an integer array of size 26 to store the first occurrence index of each letter, initializing all entries to -1 to indicate unseen letters.

Scan the string

Iterate through s by index. For each character, if it's the first occurrence, store the index in the tracking array. If it's the second occurrence, calculate the number of letters between the two indices and compare it to distance[letterIndex]. Return false immediately if it doesn't match.

Return final result

After completing the scan, if no mismatches are found, return true. This ensures that every letter pair in s meets the required distance pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the length of s, as each character is visited once. Space complexity is O(1) because the fixed-size array of 26 letters is used regardless of input size.

What Interviewers Usually Probe

Looking for correct use of a fixed-size hash or array to track first occurrences
Expecting early termination upon detecting a distance mismatch
Confirming understanding of converting letters to array indices for distance lookup

Common Pitfalls or Variants

Common pitfalls

Forgetting to subtract indices correctly to count letters between occurrences
Not handling letters that do not appear in s correctly
Reinitializing tracking array inside the loop causing incorrect first occurrence tracking

Follow-up variants

Letters may appear more than twice and distance rules may apply to first and last occurrences only
Distance array may contain -1 to indicate letters that can be ignored
Input string could include uppercase letters requiring normalization before indexing

FAQ

What is the main pattern for solving Check Distances Between Same Letters?

Use array scanning plus a hash lookup or fixed-size array to track the first occurrence of each letter and compare distances.

How do I calculate the distance between letters?

Subtract the index of the first occurrence from the second occurrence and subtract one to count letters in between, then compare to distance array.

What if a letter in the alphabet does not appear in the string?

Its corresponding distance value can be ignored; only letters present in s must meet the distance requirement.

Can this approach handle any string length?

Yes, as long as each letter appears exactly twice and the string length is within the constraints 2 <= s.length <= 52.

What is a common failure mode in this problem?

Miscounting the letters between occurrences or resetting the tracking array incorrectly, leading to false negatives.

terminal

Solution

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`.

1

2

3

4

5

6

7

8

9

class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        d = defaultdict(int)
        for i, c in enumerate(map(ord, s), 1):
            j = c - ord("a")
            if d[j] and i - d[j] - 1 != distance[j]:
                return False
            d[j] = i
        return True

Continue Practicing

#2418 sort the people #2353 design a food rating system #2451 odd string difference