# Check Distances Between Same Letters
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-distances-between-same-letters)
Canonical: https://scaleengineer.com/dsa/problems/check-distances-between-same-letters
**Data structures:** Array, Hash Table, String
---
## 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` _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
## 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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Single Pass with an Array
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public boolean checkDistances(String s, int[] distance) {
        int[] firstIndex = new int[26];
        Arrays.fill(firstIndex, -1);

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int charIndex = c - 'a';

            if (firstIndex[charIndex] == -1) {
                // First occurrence of this character
                firstIndex[charIndex] = i;
            } else {
                // Second occurrence of this character
                int expectedDistance = distance[charIndex];
                int actualDistance = i - firstIndex[charIndex] - 1;
                if (actualDistance != expectedDistance) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  boolean checkDistances(String s, int[] distance) {
    int[] d = new int[26];
    for (int i = 1, n = s.length(); i <= n; ++i) {
      int j = s.charAt(i - 1) - 'a';
      if (d[j] > 0 && i - d[j] - 1 != distance[j]) {
        return false;
      }
      d[j] = i;
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool checkDistances(string s, vector<int> &distance) {
    int d[26]{};
    for (int i = 1; i <= s.size(); ++i) {
      int j = s[i - 1] - 'a';
      if (d[j] && i - d[j] - 1 != distance[j]) {
        return false;
      }
      d[j] = i;
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    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

```