Check Distances Between Same Letters

EASY

Description

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

Checkout 2 different approaches to solve Check Distances Between Same Letters. Click on different approaches to view the approach and algorithm in detail.

Brute-Force with Nested Loops

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.

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.

class Solution {
    public boolean checkDistances(String s, int[] distance) {
        boolean[] visited = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            int charIndex = c1 - 'a';

            if (visited[charIndex]) {
                continue;
            }

            for (int j = i + 1; j < s.length(); j++) {
                char c2 = s.charAt(j);
                if (c1 == c2) {
                    if (j - i - 1 != distance[charIndex]) {
                        return false;
                    }
                    visited[charIndex] = true;
                    break; // Found the pair, move to the next character in the outer loop
                }
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Check Distances Between Same Letters. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Check Distances Between Same Letters

Data Structures:

ArrayHash TableString