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] <= 50In #2399 Check Distances Between Same Letters, you are given a string and an array describing the required distance between two identical characters. The goal is to verify whether the number of characters between the two occurrences of each letter matches the value provided in the distance array.
A practical approach is to scan the string once while keeping track of the first occurrence index of each character. This can be done using a small array or hash table of size 26 since the input consists of lowercase English letters. When a character appears for the first time, store its index. When the same character appears again, compute the number of characters in between using currentIndex - previousIndex - 1 and compare it with the expected value from distance[char].
If any character’s computed gap does not match the required distance, the condition fails immediately. Since the string is traversed only once and the auxiliary structure is constant-sized, this method achieves O(n) time complexity with O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single Pass with Array / Hash Table for First Occurrence | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Create an integer array of size 26 to keep track of the first occurrence of each letter.
The number of letters between indices i and j is j - i - 1.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
While this exact problem may not always appear, similar string and hash table validation problems are common in FAANG-style interviews. Practicing it helps build skills in string traversal, indexing logic, and constant-space optimization.
A fixed-size array of length 26 works best because the string contains only lowercase English letters. It allows constant-time storage and lookup of the first occurrence index for each character.
The optimal approach scans the string once while storing the first index of each character. When the character appears again, calculate the gap between the two positions and compare it with the expected value in the distance array. This ensures an O(n) time complexity solution.
The problem defines distance as the number of characters between the two identical letters. Therefore, the correct calculation is currentIndex minus previousIndex minus one, which excludes the two characters themselves.