2399. Check Distances Between Same Letters

EasyArrayHash TableString
Leetcode Link

Problem Description

You are tasked with determining if a given string s is "well-spaced". A string is well-spaced if it follows a specific distance rule. The string s only contains lowercase English letters, and each letter appears exactly twice in the string. In addition to the string, you're given an integer array distance with 26 elements corresponding to the letters of the English alphabet, which are indexed from 0 for 'a' to 25 for 'z'.

The distance rule is as follows: The number of letters between the two occurrences of any given letter in the string must equal the value specified in the distance array. For instance, if s has two 'a's and the distance[0] (since 'a' corresponds to index 0) is 3, there should be exactly three letters between the two 'a's in s. The rule applies to all letters present in s, and you do not need to consider distance values for letters that do not appear in s.

Your goal is to return true if the string meets this well-spaced criterion for all the letters it contains. Otherwise, you will return false.

Intuition

To verify if the string s is well-spaced according to the given distance array, you need to track the position of each letter's first appearance and check the spacing when you find its second appearance.

By iterating through the string, each time you encounter a character, check if it's the first or second appearance. If it's the first appearance, you record its position (index). If it's the second appearance, you calculate the number of characters between this and the first appearance. You then compare this calculated number with the corresponding value in the distance array.

To efficiently keep track of the positions, you can use a dictionary d, mapping each character to its first occurrence index. As you go through the string, you update the dictionary with the current position for the first occurrence. Upon finding the second occurrence of a letter, you immediately check if the distance between the first and second occurrence matches the distance value for that letter. If there's a mismatch for any letter, you return false right away since the string is not well-spaced. If no mismatch is found throughout the string, you return true after the iteration.

The ord(c) - ord('a') part of the solution is used to convert a character to its corresponding distance index (i.e., 'a' to 0, 'b' to 1, and so on).

Using a dictionary for tracking allows for an efficient solution with just one pass through the string, making the algorithm run in linear time relative to the length of the string.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Solution Approach

The solution implements a straightforward and efficient approach to check if the given string s is well-spaced according to the distance array. Here's a step-by-step explanation of how the code works:

  • The solution first initializes a dictionary d using defaultdict(int) from the collections module. This dictionary will keep track of the first occurrence index of each letter in the string.

  • Then, it iterates over each character c in the string s along with its index i (1-indexed, because we want to compute the number of letters between the occurrences, not the distance in terms of indices). The enumerate function is essential here as it provides both the character and its index in one go.

  • Inside the loop, for each character c encountered, the code checks if it's already present in the dictionary d (which would mean this is its second occurrence).

    • If it is not in the dictionary, it means this is the first time the character has appeared, so the current index i is recorded in d[c].

    • If it is present, meaning this is the second occurrence, the code immediately calculates the distance between the two occurrences. This is done by subtracting d[c] (where the first occurrence of c was recorded) from the current index i and subtracting one more to account for the character itself (since we want the number of characters between the first and second occurrences).

  • After calculating the distance between occurrences for the character c, the code compares this number to the expected distance provided in the distance array. If the calculated distance does not match the expected distance value, which is distance[ord(c) - ord('a')] (turns the letter c into its respective alphabet index), the function returns False indicating that s isn't a well-spaced string.

  • If the iteration completes without returning False, it means all characters in s satisfy the well-spaced criteria, and the function finally returns True.

This solution uses a dictionary, which is a hash map, to store and access the first occurrence indices of the characters efficiently. The decision to check the distance immediately upon the second occurrence of each character ensures that we don't need a second pass through the string or additional storage, leading to a time complexity of O(n), where n is the length of the string, and a constant space complexity since the dictionary will store at most one entry per unique character in s.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have a string s = "aibjca" and a distance array such that distance[0] = 2, distance[1] = 2, distance[2] = 1, and distance[3] = 1 (all other values in distance array are irrelevant since the corresponding characters are not in s). We need to verify if s is well-spaced according to the distance rule defined.

Now we walk through the solution steps using this example:

  1. Initialize a dictionary d to track the first occurrence index of each letter.

  2. Start iterating over the string s:

    • Index 1: c = 'a'. 'a' is not in d, so we add 'a' with its index d['a'] = 1.

    • Index 2: c = 'i'. 'i' is not in d, so we add 'i' with its index d['i'] = 2.

    • Index 3: c = 'b'. 'b' is not in d, so we add 'b' with its index d['b'] = 3.

    • Index 4: c = 'j'. 'j' is not in d, so we add 'j' with its index d['j'] = 4.

    • Index 5: c = 'c'. 'c' is not in d, so we add 'c' with its index d['c'] = 5.

    • Index 6: c = 'a'. 'a' is in d, so we check the spacing. The first occurrence was at index 1, and the current index is 6. The distance between them is 6 - 1 - 1 = 4, but distance[0] (distance for 'a') is 2. The calculated distance doesn't match the expected distance, so we return False.

If, however, the distance for 'a' was given as 4, then the example would continue as:

  • Index 7: c = 'i'. 'i' is in d, so we check the spacing. The first occurrence was at index 2, and the current index is 7. The distance between them is 7 - 2 - 1 = 4, which does not match distance[8] = 2 (distance for 'i'), we return False.

  • Index 8: c = 'b'. 'b' is in d, so we check the spacing. The first occurrence was at index 3, and the current index is 8. The distance between them is 8 - 3 - 1 = 4, which does not match distance[1] = 2 (distance for 'b'), we return False.

  • Index 9: c = 'j'. 'j' is in d, so we check the spacing. The first occurrence was at index 4, and the current index is 9. The distance between them is 9 - 4 - 1 = 4, which does not match distance[9] = 1 (distance for 'j'), we return False.

No exact matches occurred, and we return False in each case, so s is not well-spaced. If all distances were to match, we would continue through the entire string and return True at the end.

This example demonstrates how the positions are recorded and how the solution approach identifies if a string is well-spaced or not by comparing the actual distance between recurring characters with the specified distances in the given distance array.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def checkDistances(self, s: str, distances: List[int]) -> bool:
5        # Dictionary to keep track of the first occurrence index of each character
6        first_occurrence = defaultdict(int)
7      
8        # Iterate through the string while enumerating, which provides both
9        # the index and the character
10        for index, char in enumerate(s, 1): # Starting index at 1 for calculation convenience
11            # If the character has been seen before and the distance constraint is not met
12            if first_occurrence[char] and index - first_occurrence[char] - 1 != distances[ord(char) - ord('a')]:
13                return False  # The distance constraint is violated
14            # Record the first occurrence index of the character
15            first_occurrence[char] = index
16          
17        # If all characters meet their distance constraints, return True
18        return True
19
1class Solution {
2    public boolean checkDistances(String s, int[] distance) {
3        // Create an array to store the positions where characters 'a' to 'z' were seen last.
4        int[] lastSeenPositions = new int[26];
5      
6        // Loop over characters of the string.
7        for (int index = 1, stringLength = s.length(); index <= stringLength; ++index) {
8            // Calculate the array index for the character (0 for 'a', 1 for 'b', etc.)
9            int charIndex = s.charAt(index - 1) - 'a';
10          
11            // If the character has been seen before (i.e., its position is recorded in lastSeenPositions)
12            // check if the current distance is equal to the distance specified in the array.
13            if (lastSeenPositions[charIndex] > 0 && index - lastSeenPositions[charIndex] - 1 != distance[charIndex]) {
14                return false; // If the distance doesn't match, return false.
15            }
16          
17            // Record the current position (index) for the character.
18            lastSeenPositions[charIndex] = index;
19        }
20      
21        // If all distances match, return true.
22        return true;
23    }
24}
25
1class Solution {
2public:
3    // This function checks if the distances between each identical pair of characters in the string 's'
4    // are as described in the 'distance' vector, where 'distance[i]' represents the distance for the character 'a' + i.
5    // Returns true if distances are as expected, false otherwise.
6  
7    bool checkDistances(string s, vector<int>& distance) {
8        // Create an array to store the most recent index (1-based) of each letter encountered in the string 's'.
9        // Initially all set to zero indicating that letters haven't been encountered yet.
10        int lastIndex[26] = {};
11      
12        // Iterate through the string characters
13        for (int i = 1; i <= s.size(); ++i) {
14            // Calculate the 0-based index of the letter in 'lastIndex' array, 'a' corresponds to 0, 'b' to 1, and so on.
15            int charIndex = s[i - 1] - 'a';
16          
17            // If the letter has been encountered before (index non-zero),
18            // and if the current distance doesn't match the expected distance from the 'distance' vector,
19            // return false because the distances don't match.
20            if (lastIndex[charIndex] && i - lastIndex[charIndex] - 1 != distance[charIndex]) {
21                return false;
22            }
23          
24            // Update the index for the current letter to the current position (1-based).
25            lastIndex[charIndex] = i;
26        }
27      
28        // If all the distances match, return true.
29        return true;
30    }
31};
32
1function checkDistances(s: string, distances: number[]): boolean {
2    // Initialize the length of the string for future use.
3    const stringLength = s.length;
4    // Create an array to keep track of the last seen position of each character.
5    const lastSeenPositions: number[] = new Array(26).fill(0);
6
7    // Loop through each character of the string.
8    for (let index = 0; index < stringLength; ++index) {
9        // Calculate the alphabet index of the current character (0 for 'a', 1 for 'b', etc.).
10        const charIndex = s.charCodeAt(index) - 'a'.charCodeAt(0);
11
12        // Check if this character has been seen before.
13        if (lastSeenPositions[charIndex] !== 0) {
14            // Calculate the actual distance between the current and the last occurrence.
15            const actualDistance = index - lastSeenPositions[charIndex];
16
17            // Compare the actual distance with the given distance in the distances array.
18            if (actualDistance !== distances[charIndex]) {
19                // If the distances do not match, return false as the condition hasn't been met.
20                return false;
21            }
22        }
23
24        // Update the last seen position of the current character.
25        lastSeenPositions[charIndex] = index + 1; // Adding 1 as we're working with 1-based positions in this approach.
26    }
27
28    // If all conditions are satisfied for each character, return true.
29    return true;
30}
31
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the length of the input string s. The function iterates over each character of the string exactly once.

Space Complexity

The space complexity of the function is O(1). This is because the additional data structure used, d, is a dictionary that holds each unique character in the string and its latest index. Since there can be at most 26 unique characters (assuming s consists of lowercase English letters), the dictionary size is bounded by a constant, which does not scale with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫