algoadvance

Leetcode 2399. Check Distances Between Same Letters

Problem Statement

You are given a 0-indexed string s consisting of only lowercase English letters, where each letter in s appears exactly twice. You also have a 0-indexed integer array distance of length 26.

Each letter in the alphabet is numbered from 0 to 25 (i.e., ‘a’ is 0, ‘b’ is 1, …, ‘z’ is 25).

In a well-spaced string, the distance between the two occurrences of the i-th letter is distance[i]. If the letter i does not appear in s, then distance[i] can be ignored.

Return true if all the letters in s are well-spaced according to distance, otherwise return false.

Example 1:

Input:
s = "abaccb"
distance = [1, 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

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

Clarifying Questions

  1. What are the constraints of the problem?
    • The string s has even length between 2 and 52 (inclusive).
    • Each distance[i] is a non-negative integer less than 50.
  2. What should the function return if the input string does not meet these constraints?
    • You can assume the input will always meet the constraints stated in the problem.

Strategy

  1. Create an integer array first_occurrences of length 26 to store the index of the first occurrence of each character.
  2. Initialize this array to -1 for all elements.
  3. Traverse the string s:
    • If the character’s first occurrence is not recorded, store its index.
    • If the character’s first occurrence is already recorded, calculate the distance between the current index and the stored index. Compare this distance with the required distance from the distance array.
    • If any required distance does not match, return false.
  4. If all distances match, return true.

Code

#include <vector>
#include <string>
using namespace std;

bool checkDistances(string s, vector<int>& distance) {
    vector<int> first_occurrences(26, -1);
    
    for (int i = 0; i < s.length(); ++i) {
        int idx = s[i] - 'a';
        if (first_occurrences[idx] == -1) {
            first_occurrences[idx] = i;
        } else {
            int required_distance = distance[idx];
            int actual_distance = i - first_occurrences[idx] - 1;
            if (required_distance != actual_distance) {
                return false;
            }
        }
    }
    
    return true;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI