Problem

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 ifs _is awell-spaced string, otherwise return _false.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5

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 <= 52
  • s consists only of lowercase English letters.
  • Each letter appears in s exactly twice.
  • distance.length == 26
  • 0 <= distance[i] <= 50

Solution

Method 1 – Index Tracking and Distance Comparison

Intuition: Since each letter appears exactly twice, we can record the index of the first occurrence for each letter, then when we see the second occurrence, check if the distance matches the required value.

Approach:

  1. Create an array of size 26 to store the first index of each letter (initialized to -1).
  2. Iterate through the string:
    • If the letter is seen for the first time, record its index.
    • If seen for the second time, check if the difference between indices minus 1 equals the required distance.
    • If not, return false.
  3. If all checks pass, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int[] idx = new int[26];
        Arrays.fill(idx, -1);
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if (idx[c] == -1) {
                idx[c] = i;
            } else {
                if (i - idx[c] - 1 != distance[c]) return false;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def checkDistances(self, s: str, distance: list[int]) -> bool:
        idx = [-1] * 26
        for i, ch in enumerate(s):
            c = ord(ch) - ord('a')
            if idx[c] == -1:
                idx[c] = i
            else:
                if i - idx[c] - 1 != distance[c]:
                    return False
        return True

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s.
  • 🧺 Space complexity: O(1)