LeetCode 2399 - Check Distances Between Same Letters

LeetCode Problem 2399

Difficulty: 🟢 Easy
Topics: Array, Hash Table, String

Solution

Problem Understanding

This problem asks us to verify whether a string follows a very specific spacing rule between repeated characters.

We are given a string s that contains only lowercase English letters. Every character that appears in the string appears exactly twice. We are also given an integer array distance of size 26, where each index corresponds to a letter of the alphabet:

• distance[0] corresponds to 'a'
• distance[1] corresponds to 'b'
• and so on until 'z'

For each character that appears in the string, we must check whether the number of characters between its two occurrences matches the expected value in the distance array.

For example, suppose the character 'a' appears at indices 2 and 5.

The number of characters between them is:

5 - 2 - 1 = 2

So 'a' is valid only if distance[0] == 2.

The goal is to return:

• true if every character satisfies its required spacing
• false otherwise

The constraints are very small:

• The maximum string length is 52
• Only lowercase English letters are used
• Every letter appears exactly twice

Because the input is tiny, almost any reasonable approach will pass. However, the problem is still useful for practicing indexing, hashing, and character mapping.

An important detail is that letters not present in the string should be ignored completely. Even if distance[i] contains some value, it does not matter unless the corresponding character appears in s.

There are several edge cases worth considering:

• Two identical letters may appear adjacent to each other, meaning the required distance is 0
• A character may appear very far apart in the string
• The first mismatch should immediately return false
• Since every character appears exactly twice, we never need to handle more than two occurrences of the same letter

Approaches

Brute Force Approach

A brute force solution would examine each character and search the rest of the string to find its second occurrence.

For every index i:

1. Take character s[i]
2. Search forward until the same character is found
3. Compute the number of letters between them
4. Compare against the required value in distance

This approach works because it directly checks the condition defined in the problem statement.

However, the search for the second occurrence may require scanning much of the string repeatedly. If the string length is n, the worst-case complexity becomes O(n²).

Although the constraints are small enough that this solution would pass, it is inefficient compared to what we can achieve.

Optimal Approach

The key observation is that we only need to remember the first position where each character appears.

When we encounter a character for the first time, we store its index.

When we encounter it again:

1. Retrieve the first index
2. Compute the number of characters between the two positions
3. Compare with the expected distance

A hash map or fixed-size array works perfectly here because there are only 26 lowercase letters.

This reduces the time complexity to linear time, O(n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans forward to find matching characters
Optimal	O(n)	O(1)	Stores first occurrence index for each character

Algorithm Walkthrough

Optimal Algorithm

1. Create a data structure to store the first occurrence index of each character.

Since there are only 26 lowercase letters, we can use either:

• a hash map
• a fixed-size array of length 26

An array is slightly simpler and faster. 2. Initialize all positions to -1.

The value -1 means the character has not been seen yet. 3. Traverse the string from left to right. 4. For each character:

• Convert the character into an integer index using:

ord(character) - ord('a')

5. Check whether this character has appeared before.

• If not, store the current index as its first occurrence.
• If yes, compute the distance between occurrences.

6. Compute the number of letters between the two positions.

If the first occurrence is at firstIndex and the current index is i, then:

actualDistance = i - firstIndex - 1

7. Compare actualDistance with the expected value from the distance array.

• If they differ, return false immediately.
• Otherwise continue scanning.

8. If the entire string is processed without mismatches, return true.

Why it works

The algorithm works because every character appears exactly twice. By storing the first occurrence of each character, we can precisely compute the spacing when the second occurrence appears.

At every second occurrence, the algorithm verifies the exact condition required by the problem. If all characters satisfy the condition, the string is well-spaced. If any character fails, the string is not well-spaced.

Python Solution

from typing import List

class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        first_seen = [-1] * 26

        for index, char in enumerate(s):
            char_index = ord(char) - ord('a')

            if first_seen[char_index] == -1:
                first_seen[char_index] = index
            else:
                actual_distance = index - first_seen[char_index] - 1

                if actual_distance != distance[char_index]:
                    return False

        return True

The implementation begins by creating an array called first_seen. Each position corresponds to a letter of the alphabet, and the value stored represents the first index where that character appeared.

As we iterate through the string, we convert each character into its alphabet index using ASCII arithmetic.

If the character has not appeared before, we store the current index.

If it has already appeared, we compute the number of characters between the two occurrences and compare it against the required value in distance.

The moment we detect a mismatch, we return False. This early termination avoids unnecessary work.

If the loop finishes successfully, every character satisfied the spacing rule, so we return True.

Go Solution

func checkDistances(s string, distance []int) bool {
	firstSeen := make([]int, 26)

	for i := 0; i < 26; i++ {
		firstSeen[i] = -1
	}

	for i, char := range s {
		charIndex := int(char - 'a')

		if firstSeen[charIndex] == -1 {
			firstSeen[charIndex] = i
		} else {
			actualDistance := i - firstSeen[charIndex] - 1

			if actualDistance != distance[charIndex] {
				return false
			}
		}
	}

	return true
}

The Go implementation follows the same logic as the Python solution.

One small difference is that Go arrays and slices default to 0, so we explicitly initialize all entries to -1 to represent unseen characters.

The range loop over the string returns rune positions and rune values. Since the input contains only lowercase English letters, rune handling is straightforward and safe here.

No integer overflow concerns exist because the maximum string length is only 52.

Worked 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]

Step-by-step Trace

Index	Character	First Seen Before?	Stored First Index	Actual Distance	Expected Distance	Result
0	a	No	0	-	1	Continue
1	b	No	1	-	3	Continue
2	a	Yes	0	1	1	Valid
3	c	No	3	-	0	Continue
4	c	Yes	3	0	0	Valid
5	b	Yes	1	3	3	Valid

All characters satisfy their required distances, so the answer is:

true

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]

Step-by-step Trace

Index	Character	First Seen Before?	Stored First Index	Actual Distance	Expected Distance	Result
0	a	No	0	-	1	Continue
1	a	Yes	0	0	1	Invalid

The actual distance is 0, but the expected distance is 1.

Therefore the answer is:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	The auxiliary array always has size 26

The algorithm performs a single pass through the string, making the running time linear in the size of the input.

The extra memory usage is constant because the storage array always contains exactly 26 entries regardless of input size.

Test Cases

from typing import List

class Solution:
    def checkDistances(self, s: str, distance: List[int]) -> bool:
        first_seen = [-1] * 26

        for index, char in enumerate(s):
            char_index = ord(char) - ord('a')

            if first_seen[char_index] == -1:
                first_seen[char_index] = index
            else:
                actual_distance = index - first_seen[char_index] - 1

                if actual_distance != distance[char_index]:
                    return False

        return True

sol = Solution()

assert sol.checkDistances(
    "abaccb",
    [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]
) == True  # provided valid example

assert sol.checkDistances(
    "aa",
    [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]
) == False  # provided invalid example

assert sol.checkDistances(
    "aa",
    [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,0]
) == True  # adjacent identical letters

assert sol.checkDistances(
    "zz",
    [0]*25 + [0]
) == True  # last alphabet character

assert sol.checkDistances(
    "aba",
    [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]
) == True  # single character pair with one letter between

assert sol.checkDistances(
    "abba",
    [2,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]
) == False  # incorrect distance for 'a'

assert sol.checkDistances(
    "bccb",
    [0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
) == False  # incorrect distance for 'c'

assert sol.checkDistances(
    "mnopmn",
    [0]*12 + [3,3,0,0] + [0]*10
) == False  # multiple characters with mismatch

Test Summary

Test	Why
"abaccb"	Validates the standard successful case
"aa" with distance 1	Validates immediate failure
"aa" with distance 0	Validates adjacent duplicate handling
"zz"	Validates correct indexing for 'z'
"aba"	Validates single-character gap calculation
"abba"	Validates mismatch detection
"bccb"	Validates inner pair distance checking
"mnopmn"	Validates handling of multiple distinct characters

Edge Cases

Adjacent identical characters

A string like "aa" is an important edge case because the distance between the two occurrences is 0. A common bug is forgetting the -1 when computing the number of characters between indices.

The implementation correctly computes:

1 - 0 - 1 = 0

which matches the intended definition.

Characters appearing far apart

A character may appear near the beginning and end of the string. Incorrect indexing logic can easily produce off-by-one errors in these situations.

The formula:

secondIndex - firstIndex - 1

correctly counts only the characters strictly between the two positions.

Characters not present in the string

The distance array always has 26 values, but many letters may not appear in the string at all.

A buggy implementation might incorrectly try to validate every alphabet character.

This implementation only checks characters encountered during traversal, so unused letters are naturally ignored, exactly as required by the problem statement.