Check Distances Between Same Letters

Easy
1798.

Check Distances Between Same Letters

Check Distances Between Same Letters is an easy coding problem on arrays, strings and hash table, asked in Amazon interviews.

You are given a lowercase string s in which every letter that appears, appears exactly twice, and an integer array distance of length 26.

Letter i of the alphabet (a is 0, b is 1, …, z is 25) is well spaced if the number of characters strictly between its two occurrences equals distance[i]. Letters that do not appear in s are ignored.

Return true if every letter in s is well spaced, and false otherwise.

Example 1

Input
s = "bccb", distance = [0,2,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
true
Explanation
The two `b`s have 2 characters between them and the two `c`s have 0, matching `distance[1] = 2` and `distance[2] = 0`.

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
The two `a`s are adjacent, with 0 characters between them, not 1.

Example 3

Input
s = "abcabc", distance = [2,2,1,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` and `b` each have 2 characters between their copies, but so does `c`, and `distance[2]` asks for 1.

Constraints

  • 2 <= s.length <= 52
  • s holds lowercase English letters; each letter in s appears exactly twice
  • distance.length == 26
  • 0 <= distance[i] <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number[]} distance
 * @return {boolean}
 */
var checkDistances = function(s, distance) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check Distances Between Same Letters — Problem & Solution

Check Distances Between Same Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Check Distances Between Same Letters is an easy coding problem on arrays, strings and hash table, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, Hash Table
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a lowercase string s in which every letter that appears, appears exactly twice, and an integer array distance of length 26.

Letter i of the alphabet (a is 0, b is 1, …, z is 25) is well spaced if the number of characters strictly between its two occurrences equals distance[i]. Letters that do not appear in s are ignored.

Return true if every letter in s is well spaced, and false otherwise.

Example 1

Input: s = "bccb", distance = [0,2,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: true
Explanation: The two `b`s have 2 characters between them and the two `c`s have 0, matching `distance[1] = 2` and `distance[2] = 0`.

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: The two `a`s are adjacent, with 0 characters between them, not 1.

Example 3

Input: s = "abcabc", distance = [2,2,1,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` and `b` each have 2 characters between their copies, but so does `c`, and `distance[2]` asks for 1.

Constraints

  • 2 <= s.length <= 52
  • s holds lowercase English letters; each letter in s appears exactly twice
  • distance.length == 26
  • 0 <= distance[i] <= 50

Hints for Check Distances Between Same Letters

  1. Hint 1

    Record the index where each letter first appears.

  2. Hint 2

    When you meet a letter the second time at index j after first seeing it at i, the gap is j - i - 1.

  3. Hint 3

    Compare that gap with distance[letter] and stop at the first mismatch.

How to solve Check Distances Between Same Letters

One pass with a 26-slot table of first positions measures every letter's gap at its second occurrence.

Approach

  1. Fill first[26] with -1.
  2. For each index j: let c be the letter. If first[c] == -1, set it to j; otherwise, if j - first[c] - 1 != distance[c], return false.
  3. Return true.

Why it works

Each letter appears exactly twice, so the second sighting closes its only gap, and j - i - 1 counts the characters strictly between positions i and j. Letters absent from s are never checked.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The distance counts characters between the copies: adjacent copies have distance 0, not 1.
  • Only letters present in s are checked; distance entries for absent letters can be anything.

Reference solution

Python

from typing import List

def checkDistances(s: str, distance: List[int]) -> bool:
    first = [-1] * 26
    for j, ch in enumerate(s):
        c = ord(ch) - 97
        if first[c] == -1:
            first[c] = j
        elif j - first[c] - 1 != distance[c]:
            return False
    return True

Java

public static boolean checkDistances(String s, int[] distance) {
    int[] first = new int[26];
    Arrays.fill(first, -1);
    for (int j = 0; j < s.length(); j++) {
        int c = s.charAt(j) - 'a';
        if (first[c] == -1) first[c] = j;
        else if (j - first[c] - 1 != distance[c]) return false;
    }
    return true;
}

C++

bool checkDistances(string s, vector<int>& distance) {
    vector<int> first(26, -1);
    for (int j = 0; j < (int)s.size(); j++) {
        int c = s[j] - 'a';
        if (first[c] == -1) first[c] = j;
        else if (j - first[c] - 1 != distance[c]) return false;
    }
    return true;
}

JavaScript

var checkDistances = function(s, distance) {
    var first = new Array(26).fill(-1);
    for (var j = 0; j < s.length; j++) {
        var c = s.charCodeAt(j) - 97;
        if (first[c] === -1) first[c] = j;
        else if (j - first[c] - 1 !== distance[c]) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings