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.
Each letter in the alphabet is numbered from 0 to 25 (i.e. 'a' -> 0, 'b' -> 1, 'c' -> 2, ... , 'z' -> 25).
In a well-spaced string, the number of letters between the two occurrences of the ith letter is distance[i]. If the ith letter does not appear in s, then distance[i] can be ignored.
Return true if s is a well-spaced string, otherwise return false.
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 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 Explanation: - '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 <= 52s consists only of lowercase English letters.s exactly twice.distance.length == 260 <= distance[i] <= 50Problem Overview: You are given a string s and an integer array distance of size 26. Each character in s appears exactly twice. The number of characters between the two occurrences of a letter must match the value stored at its index in distance. The task is to verify whether the string satisfies this rule for every character.
Approach 1: Using Sorting (O(n log n) time, O(n) space)
This method records the indices where each character appears, then sorts the recorded pairs of indices to compute distances. You first iterate through the string and push (character, index) pairs into a list. After sorting by character, identical letters become adjacent, making it easy to calculate the gap between their indices. For each pair, compute index2 - index1 - 1 and compare it with distance[char - 'a']. Sorting introduces O(n log n) time complexity, while storing indices requires O(n) extra space. This approach is straightforward and works well when you're already manipulating ordered character-index pairs.
Approach 2: Using Hash Map (O(n) time, O(1) space)
A more efficient solution stores the first occurrence of each character using a hash map (or fixed array of size 26). Iterate through the string once. When you encounter a character for the first time, record its index. When you see it again, compute the distance between the two positions using currentIndex - firstIndex - 1 and compare it with the expected value in the distance array. Because each lookup in the hash map is O(1), the full scan runs in linear time. The extra memory stays constant since only 26 lowercase letters are possible.
This approach relies on fast lookups and a single pass over the string, which is why it is commonly categorized under hash table and string problems. The input array is also accessed directly as an array, keeping operations simple and cache-friendly.
Recommended for interviews: The hash map approach. Interviewers expect candidates to recognize that only the first index of each character matters. Recording it and validating the distance during the second occurrence produces an O(n) solution with constant space. Discussing the sorting approach first can demonstrate baseline reasoning, but implementing the hash map version shows stronger algorithmic thinking and familiarity with common string-processing patterns.
This solution uses C's built-in qsort function to sort the array. This function takes a comparator function that defines the sorting order. Sorting is followed by operations that can leverage the sorted nature of the array.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting is done in-place.
This C program creates a simple hash table to count occurrences of elements. Given constraints are necessary for defining the hash table size.
Time Complexity: O(n) for processing elements.
Space Complexity: O(k) where k is the range of input values.
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.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(|\Sigma|), where \Sigma is the character set, which in this case is the set of lowercase letters.
| Approach | Complexity |
|---|---|
| Approach 1: Using Sorting | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Using Hash Map | Time Complexity: O(n) for processing elements. |
| Array or Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting Character Indices | O(n log n) | O(n) | When storing and processing ordered character-index pairs or when sorting is already part of the pipeline |
| Hash Map / First Occurrence Tracking | O(n) | O(1) | General case and interview settings where linear scan with constant memory is preferred |
2399. Check Distances Between Same Letters | Leetcode Weekly Contest 309 | LeetCode 2399 • Bro Coders • 1,769 views views
Watch 9 more video solutions →Practice Check Distances Between Same Letters with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor