Problem Description

You are given a string s where every lowercase letter that appears in the string appears exactly twice. You are also given an array distance of length 26, where each position corresponds to a letter of the alphabet ('a' at index 0, 'b' at index 1, and so on).

A string is considered "well-spaced" if, for each letter that appears in the string, the number of letters between its two occurrences equals the value specified in the distance array for that letter.

For example, if the letter 'a' appears at positions 1 and 4 in the string, there are 2 letters between them (positions 2 and 3). This would be valid only if distance[0] = 2.

Your task is to determine if the given string s is well-spaced according to the distance array. Return true if it is well-spaced, otherwise return false.

Key points to understand:

• Each letter in s appears exactly twice
• The distance between two occurrences of a letter is the count of letters between them (not including the letter itself)
• If a letter doesn't appear in s, its corresponding value in distance can be ignored
• Letters are mapped to indices: 'a' → 0, 'b' → 1, ..., 'z' → 25

Intuition

Since each letter appears exactly twice in the string, we need to track where we first see each letter and then verify the distance when we encounter it the second time.

The key insight is that we don't need to store both positions for each letter. When we see a letter for the first time, we just record its position. When we see it again, we can immediately calculate the distance between the two occurrences and check if it matches the required distance.

Think of it like marking checkpoints: as we traverse the string from left to right, we place a marker when we first see a letter. When we see that same letter again, we measure how far we've traveled since the marker and verify if it matches our expected distance.

The distance between two occurrences at positions i and j (where j > i) is j - i - 1. For example, if a letter appears at position 2 and position 5, the distance is 5 - 2 - 1 = 2 (there are 2 letters between them).

This leads to a single-pass solution: iterate through the string once, and for each character:

• If we haven't seen it before, record its position
• If we have seen it before, calculate the distance and verify it matches the expected value
• If any distance doesn't match, we can immediately return false
• If we complete the traversal without issues, the string is well-spaced

Using a hash table or array to store the first occurrence positions makes this checking process efficient with O(n) time complexity where n is the length of the string.

Solution Approach

The solution uses a hash table (or dictionary) to track the first occurrence of each letter and validates the distance when encountering the second occurrence.

Implementation walkthrough:

1. Initialize a hash table d using defaultdict(int) to store the position of the first occurrence of each letter. The default value of 0 helps us identify if we've seen a letter before.

2. Iterate through the string using enumerate(map(ord, s), 1):

   • We use enumerate starting from 1 (not 0) to make position tracking easier
   • map(ord, s) converts each character to its ASCII value for easier calculation
   • For each character at position i, we get its ASCII value c

3. Convert character to alphabet index: Calculate j = c - ord("a") to get the 0-based index for the letter (0 for 'a', 1 for 'b', etc.)

4. Check if this is the second occurrence:

   • If d[j] is non-zero, we've seen this letter before
   • Calculate the distance: i - d[j] - 1
     • i is the current position (1-indexed)
     • d[j] is the first occurrence position (1-indexed)
     • Subtract 1 to get the number of letters between them
   • Compare with distance[j] - if they don't match, return False

5. Record the position: If this is the first occurrence (or after checking the second), set d[j] = i

6. Return the result: If we complete the iteration without finding any mismatches, return True

Example walkthrough: For string "abaccb" with distance = [2, 3, 0, ...]:

• Position 1: 'a' → Store d[0] = 1
• Position 2: 'b' → Store d[1] = 2
• Position 3: 'a' → Check: 3 - 1 - 1 = 1 ≠ 2, return False

The algorithm runs in O(n) time where n is the length of the string, with O(1) space since we store at most 26 letters.

Example Walkthrough

Let's walk through the solution with a concrete example to understand how it works.

Example Input:

• String s = "abccba"
• Distance array distance = [4, 2, 1, ...] (showing first 3 values for letters a, b, c)

Step-by-step execution:

Starting with an empty hash table d = {} to track first occurrences.

Position 1 (index 0): Character 'a'

• Convert 'a' to index: j = ord('a') - ord('a') = 0
• Check d[0]: It's 0 (not seen before)
• Store first occurrence: d[0] = 1
• Hash table: d = {0: 1}

Position 2 (index 1): Character 'b'

• Convert 'b' to index: j = ord('b') - ord('a') = 1
• Check d[1]: It's 0 (not seen before)
• Store first occurrence: d[1] = 2
• Hash table: d = {0: 1, 1: 2}

Position 3 (index 2): Character 'c'

• Convert 'c' to index: j = ord('c') - ord('a') = 2
• Check d[2]: It's 0 (not seen before)
• Store first occurrence: d[2] = 3
• Hash table: d = {0: 1, 1: 2, 2: 3}

Position 4 (index 3): Character 'c' (second occurrence)

• Convert 'c' to index: j = ord('c') - ord('a') = 2
• Check d[2]: It's 3 (seen before at position 3)
• Calculate distance: 4 - 3 - 1 = 0
• Compare with distance[2] = 1: 0 ≠ 1
• Return False - The string is not well-spaced!

The algorithm detected that the two 'c' characters are adjacent (0 letters between them), but the distance array requires 1 letter between them. Therefore, the string "abccba" is not well-spaced according to the given distance requirements.

Alternative scenario: If the string were "abcbca" with the same distance array:

• 'a' appears at positions 1 and 6: distance = 6 - 1 - 1 = 4 ✓ (matches distance[0])
• 'b' appears at positions 2 and 4: distance = 4 - 2 - 1 = 1 ✗ (doesn't match distance[1] = 2)
• Result: False

This demonstrates how the algorithm efficiently checks distances in a single pass through the string.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through the string exactly once using the enumerate function, and for each character, it performs constant-time operations: calculating the character index j, checking if the character has been seen before, comparing distances, and updating the dictionary.

The space complexity is O(|Σ|), where Σ is the character set (lowercase English letters in this case). The dictionary d can store at most 26 entries, one for each lowercase letter from 'a' to 'z', regardless of the input string length. Since the size of the alphabet is constant (26), this can also be expressed as O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Distance Calculation (Off-by-One Error)

The most common mistake is incorrectly calculating the distance between two occurrences of a letter. Many developers confuse:

• The number of positions between two indices
• The difference between two indices
• Whether to use 0-indexed or 1-indexed positions

Incorrect implementations:

# Pitfall 1: Forgetting to subtract 1
actual_distance = position2 - position1  # Wrong! This includes both positions

# Pitfall 2: Using 0-indexed positions incorrectly
for i, char in enumerate(s):  # i is 0-indexed
    if first_occurrence[char_index] is not None:
        actual_distance = i - first_occurrence[char_index] - 1  # Wrong calculation!

Why this happens: When positions are 0-indexed, if 'a' appears at positions 0 and 3, the difference is 3, but there are only 2 letters between them (positions 1 and 2).

Solution: Use consistent indexing throughout. The provided solution uses 1-indexed positions with enumerate(s, 1), making the calculation intuitive: distance = current_pos - first_pos - 1.

2. Using Wrong Default Values in Dictionary

Incorrect implementation:

first_occurrence = {}  # or dict()

for position, char in enumerate(s, 1):
    char_index = ord(char) - ord('a')
  
    if char_index in first_occurrence:  # Need to check existence
        # calculate distance
    else:
        first_occurrence[char_index] = position

Problem: Using a regular dictionary requires explicit checking with in operator. If you use if first_occurrence[char_index]: with a regular dict, it will raise a KeyError.

Solution: Use defaultdict(int) which returns 0 for missing keys. Since positions start from 1, a value of 0 clearly indicates "not seen yet", making the code cleaner and avoiding the need for existence checks.

3. Confusing Character Index with Position

Incorrect implementation:

for i, char in enumerate(s):
    if first_occurrence[char]:  # Using character as key instead of index
        actual_distance = i - first_occurrence[char] - 1

Problem: Mixing up the character itself with its alphabetical index leads to incorrect dictionary keys and wrong distance array lookups.

Solution: Always convert the character to its alphabetical index: char_index = ord(char) - ord('a') and use this consistently for both dictionary access and distance array indexing.