Check Distances Between Same Letters

Easy

#2183Time: O(N^2), where N is the length of the string `s`. In the worst case, for each character, we might scan the rest of the string to find its pair. For a string like 'abccba', the outer loop for 'a' will cause the inner loop to scan almost the entire string.Space: O(1). We use a boolean array `visited` of size 26, which is constant space and does not depend on the input string's length.

Data structures

Array Hash Table String

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the string to find the first occurrence of each character. For each character found, it then performs a nested scan to find its second occurrence. Once both occurrences are found, the distance is calculated and compared against the required distance. To avoid redundant checks for the same letter, a visited array is used.

Algorithm

Initialize a boolean array visited of size 26 to all false.
Iterate through the string s with an index i from 0 to s.length() - 1.
For each character c = s.charAt(i), get its alphabet index charIndex = c - 'a'.
If visited[charIndex] is true, it means we have already checked this character, so we continue to the next iteration.
If visited[charIndex] is false, start a nested loop with index j from i + 1 to s.length() - 1 to find the second occurrence of c.
If s.charAt(j) equals c, we have found the pair.
Calculate the distance between them: j - i - 1.
Compare this calculated distance with distance[charIndex]. If they are not equal, the string is not well-spaced, so return false.
If they are equal, mark the character as visited by setting visited[charIndex] = true and break the inner loop.
If the outer loop completes without returning false, it means all character pairs are well-spaced. Return true.

Walkthrough

We can solve this problem by checking each character that appears in the string s. A straightforward way is to iterate through the string and, for each character, find its matching pair. To avoid re-checking characters, we use a boolean array visited of size 26. visited[i] will be true if we have already checked the distance for the i-th letter of the alphabet.

1class Solution {2    public boolean checkDistances(String s, int[] distance) {3        boolean[] visited = new boolean[26];4        for (int i = 0; i < s.length(); i++) {5            char c1 = s.charAt(i);6            int charIndex = c1 - 'a';7 8            if (visited[charIndex]) {9                continue;10            }11 12            for (int j = i + 1; j < s.length(); j++) {13                char c2 = s.charAt(j);14                if (c1 == c2) {15                    if (j - i - 1 != distance[charIndex]) {16                        return false;17                    }18                    visited[charIndex] = true;19                    break; // Found the pair, move to the next character in the outer loop20                }21            }22        }23        return true;24    }25}

Complexity

Time

O(N^2), where N is the length of the string `s`. In the worst case, for each character, we might scan the rest of the string to find its pair. For a string like 'abccba', the outer loop for 'a' will cause the inner loop to scan almost the entire string.

Space

O(1). We use a boolean array `visited` of size 26, which is constant space and does not depend on the input string's length.

Trade-offs

Pros

Simple to understand and implement.
Uses constant extra space.

Cons

Inefficient for large strings due to the O(N^2) time complexity. Although it passes for the given constraints, it's not the optimal solution.

A more efficient approach involves a single pass through the string. We use an auxiliary data structure, like an array or a hash map, to store the index of the first occurrence of each character. When we encounter the second occurrence of a character, we can instantly calculate the distance and verify it.

Algorithm

Initialize an integer array firstIndex of size 26 with all elements set to a sentinel value like -1.
Iterate through the string s with an index i from 0 to s.length() - 1.
For each character c = s.charAt(i), get its alphabet index charIndex = c - 'a'.
Check the value at firstIndex[charIndex].
If firstIndex[charIndex] is -1, it's the first time we've seen this character. Store its index: firstIndex[charIndex] = i.
If firstIndex[charIndex] is not -1, this is the second occurrence. The first occurrence was at index firstIndex[charIndex].
Calculate the actual distance: i - firstIndex[charIndex] - 1.
Compare this actual distance with the expected distance distance[charIndex]. If they don't match, return false.
If the loop finishes, it means all character pairs satisfied their distance requirements. Return true.

Walkthrough

This optimized approach avoids the nested loop by remembering the position of the first time we see a character. This allows for a constant-time lookup to find the distance once the second character is found. We can use an integer array, say firstIndex, of size 26. We initialize it with a sentinel value (e.g., -1) to indicate that we haven't seen any character yet.

1import java.util.Arrays;2 3class Solution {4    public boolean checkDistances(String s, int[] distance) {5        int[] firstIndex = new int[26];6        Arrays.fill(firstIndex, -1);7 8        for (int i = 0; i < s.length(); i++) {9            char c = s.charAt(i);10            int charIndex = c - 'a';11 12            if (firstIndex[charIndex] == -1) {13                // First occurrence of this character14                firstIndex[charIndex] = i;15            } else {16                // Second occurrence of this character17                int expectedDistance = distance[charIndex];18                int actualDistance = i - firstIndex[charIndex] - 1;19                if (actualDistance != expectedDistance) {20                    return false;21                }22            }23        }24        return true;25    }26}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string only once, and all operations inside the loop are constant time.

Space

O(1). We use an integer array `firstIndex` of size 26, which is constant space as its size does not depend on the input string length.

Trade-offs

Pros

Optimal time complexity of O(N).
Efficient and clean implementation.
Uses constant extra space.

Cons

Requires a small amount of extra space for the index-tracking array, though it's constant and negligible.

Solutions

Solution

1class Solution {2public3  boolean checkDistances(String s, int[] distance) {4    int[] d = new int[26];5    for (int i = 1, n = s.length(); i <= n; ++i) {6      int j = s.charAt(i - 1) - 'a';7      if (d[j] > 0 && i - d[j] - 1 != distance[j]) {8        return false;9      }10      d[j] = i;11    }12    return true;13  }14}

1class Solution {2public:3  bool checkDistances(string s, vector<int> &distance) {4    int d[26]{};5    for (int i = 1; i <= s.size(); ++i) {6      int j = s[i - 1] - 'a';7      if (d[j] && i - d[j] - 1 != distance[j]) {8        return false;9      }10      d[j] = i;11    }12    return true;13  }14};

1class Solution:2    def checkDistances(self, s: str, distance: List[int]) -> bool: d = defaultdict(int) for i, c in enumerate(s, 1): if d[c] and i - d[c] - 1 != distance[ord(c) - ord('a')]: return False d[c] = i return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem