algoadvance

Leetcode 2399. Check Distances Between Same Letters

Problem Statement

Given a 0-indexed string s consisting of only lowercase English letters, you need to determine whether the distances between the same letters in s are consistent with the provided distances array.

In detail, for each s[i] and s[j] with s[i] == s[j] and i < j, the distance between i and j should equal distances[s[i]-'a']. Here, distances is an array of length 26 where distances[i] contains the desired distance between the occurrences of the character ('a' + i) if such a character is in the string.

Return true if the distances match for all matching characters, otherwise, return false.

Example

Example 1:

Input: s = "abaccb", distances = [1, 3, 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 letter 'a' occurs at indices 0 and 2, and the distance between them is 2 - 0 - 1 = 1. The letter 'b' occurs at indices 1 and 5, and the distance between them is 5 - 1 - 1 = 3.
- For 'c' there is only one occurrence at index 2 and 3, so we do not need to check anything for 'c'.
Thus, the output is true.

Clarifying Questions

  1. Can s be empty?
    • No, assume s will have at least one character as it will always have valid input.
  2. Can distances have any invalid values or will it always contain 26 non-negative integers?
    • distances will always have 26 non-negative integers.

Strategy

  1. Create an array lastIndex initialized to -1 of size 26 to hold the last seen index of each character.
  2. Iterate through the string, for each character c at index i:
    • Calculate its position pos = c - 'a'.
    • If lastIndex[pos] is not -1, then check if the distance between current index i and lastIndex[pos] is equal to distances[pos] + 1. If not, return false.
    • Update lastIndex[pos] with the current index i.

If all checks pass, return true.

Code

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

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

            if (lastIndex[pos] != -1) {
                if ((i - lastIndex[pos] - 1) != distances[pos]) {
                    return false;
                }
            }
            lastIndex[pos] = i;
        }

        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        String s1 = "abaccb";
        int[] distances1 = {1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        System.out.println(sol.checkDistances(s1, distances1)); // Output: true
    }
}

Time Complexity

This method ensures that we efficiently check each character and its distances in one pass through the string.

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