Solution Explanation: Checking Distances Between Same Letters

This problem asks us to determine if a given string s is "well-spaced" based on a distance array. A well-spaced string means that for each letter, the number of letters between its two occurrences matches the value specified in the distance array at the corresponding letter's index (a=0, b=1, etc.).

Approach:

The most efficient approach uses a hash table (or a simple array in this case since we only have 26 lowercase letters). We iterate through the string, recording the index of each letter's first occurrence. When we encounter a letter again, we calculate the distance between the two occurrences and compare it to the specified distance in the distance array.

Algorithm:

1. Initialization: Create an array d of size 26, initialized to 0. This array will store the indices of the first occurrence of each letter.

2. Iteration: Iterate through the string s:

   • For each character c, calculate its index j (e.g., 'a' -> 0, 'b' -> 1).
   • If d[j] is not 0 (meaning we've seen this letter before):
     • Calculate the distance between the current index and the previously recorded index (i - d[j] - 1).
     • If this distance does not match distance[j], the string is not well-spaced; return false.
   • Otherwise (first occurrence of the letter), set d[j] to the current index i.

3. Return True: If the loop completes without finding any mismatches, the string is well-spaced; return true.

Time Complexity Analysis:

The algorithm iterates through the string once, performing constant-time operations for each character. Therefore, the time complexity is O(n), where n is the length of the string.

Space Complexity Analysis:

The space complexity is O(1) because we use a fixed-size array d of size 26 (regardless of the input string length).

Code Examples (Python and Java):

Python:

from collections import defaultdict
 
class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        d = defaultdict(int)  # Use defaultdict for cleaner handling of missing keys
        for i, c in enumerate(s):
            j = ord(c) - ord('a')
            if d[j]: #If we've seen the character before
                if i - d[j] - 1 != distance[j]:
                    return False
            else:
                d[j] = i
        return True
 

Java:

class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int[] d = new int[26];
        for (int i = 0; i < s.length(); i++) {
            int j = s.charAt(i) - 'a';
            if (d[j] != 0) {
                if (i - d[j] - 1 != distance[j]) {
                    return false;
                }
            } else {
                d[j] = i + 1; // +1 to make it 1-based indexing
            }
        }
        return true;
    }
}

The other language examples provided in the original response follow the same basic algorithm and have similar complexity characteristics. The choice of data structure (array vs. hashmap) is largely a matter of preference and language conventions, given the small and fixed size of the alphabet. An array is often slightly more efficient in this specific case.