Check Distances Between Same Letters

Difficulty: Easy | Acceptance: 71.50% | Paid: No Topics: Array, Hash Table, String

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.

The array distance indicates the number of letters between the two occurrences of each letter in s. Specifically, distance[0] represents the number of letters between the two ‘a’s, distance[1] represents the number of letters between the two ‘b’s, and so on.

Return true if s is a well-spaced string, otherwise return false.

• Examples
• Constraints
• Hash Map Approach
• Array Tracking Approach
• Two-Pass Approach

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
Explanation:
- 'a' appears at indices 0 and 2 with distance 1 (index 2 - index 0 - 1 = 1).
- 'b' appears at indices 1 and 5 with distance 3 (index 5 - index 1 - 1 = 3).
- 'c' appears at indices 3 and 4 with distance 0 (index 4 - index 3 - 1 = 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:
- 'a' appears at indices 0 and 1 with distance 0 (index 1 - index 0 - 1 = 0).
- But distance[0] = 1, which does not match.

Constraints

2 <= s.length <= 52
s consists only of lowercase English letters.
Each letter appears exactly twice in s.
distance.length == 26
0 <= distance[i] <= 50

Hash Map Approach

Intuition Use a hash map to store the first occurrence index of each character, then verify the distance when encountering the second occurrence.

Steps

• Initialize a hash map to store first occurrence indices
• Iterate through the string with index tracking
• If character not in map, store its index
• If character already in map, calculate distance and compare with given array
• Return false if any mismatch, true otherwise

class Solution:
    def checkDistances(self, s: str, distance: list[int]) -> bool:
        first_occurrence = {}
        for i, char in enumerate(s):
            if char in first_occurrence:
                expected_dist = distance[ord(char) - ord('a')]
                actual_dist = i - first_occurrence[char] - 1
                if actual_dist != expected_dist:
                    return False
            else:
                first_occurrence[char] = i
        return True

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) since we store at most 26 characters
• Notes: Hash map provides O(1) average lookup time

Array Tracking Approach

Intuition Since we only have 26 lowercase letters, use a fixed-size array instead of a hash map for better cache locality.

Steps

• Initialize an array of size 26 with -1 to indicate unseen characters
• Iterate through the string
• If character’s position is -1, store current index
• Otherwise, calculate and verify the distance
• Return result based on all checks

class Solution:
    def checkDistances(self, s: str, distance: list[int]) -> bool:
        first_occurrence = [-1] * 26
        for i, char in enumerate(s):
            idx = ord(char) - ord('a')
            if first_occurrence[idx] == -1:
                first_occurrence[idx] = i
            else:
                actual_dist = i - first_occurrence[idx] - 1
                if actual_dist != distance[idx]:
                    return False
        return True

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) fixed array of 26 elements
• Notes: Better cache performance than hash map approach

Two-Pass Approach

Intuition First pass records all first occurrences, second pass validates all distances for cleaner separation of concerns.

Steps

• First pass: record the index of first occurrence for each character
• Second pass: for each character, find its second occurrence and verify distance
• Return true if all distances match

class Solution:
    def checkDistances(self, s: str, distance: list[int]) -> bool:
        first_occurrence = [-1] * 26
        # First pass: record first occurrences
        for i, char in enumerate(s):
            idx = ord(char) - ord('a')
            if first_occurrence[idx] == -1:
                first_occurrence[idx] = i
        # Second pass: verify distances
        for i, char in enumerate(s):
            idx = ord(char) - ord('a')
            if i != first_occurrence[idx]:
                actual_dist = i - first_occurrence[idx] - 1
                if actual_dist != distance[idx]:
                    return False
        return True

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) fixed array of 26 elements
• Notes: Two passes through the string but same asymptotic complexity