We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check Distances Between Same Letters

Difficulty: Easy

Problem Description

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, ..., '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.

Key Insights

  • Each letter in the string s appears exactly twice.
  • The distance between the first and second occurrence of each letter must match the corresponding value in the distance array.
  • If a letter does not appear in the string, its distance can be ignored.
  • The input string length is guaranteed to be even, as each letter appears twice.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. We traverse the string once to gather indices and check distances. Space Complexity: O(1), since we only use a fixed-size array to store indices for the letters.

Solution

To solve the problem, we will:

  1. Create an array of size 26 to store the indices of the first occurrences of each letter.
  2. Traverse the string s and for each letter:
    • Record its first occurrence index if it's the first time we've seen it.
    • If it's the second occurrence, calculate the distance between the two indices.
  3. Compare the calculated distance with the corresponding value in the distance array.
  4. If any distance does not match, return false; otherwise, return true.

We will use an array to store the first occurrence index of letters, which allows us to efficiently check the required distances.

Code Solutions

def checkDistances(s: str, distance: List[int]) -> bool:
    # Initialize an array to store the first occurrence index of each letter
    index = [-1] * 26
    
    for i, char in enumerate(s):
        idx = ord(char) - ord('a')  # Get the index for the character
        if index[idx] == -1:
            index[idx] = i  # Store the index of first occurrence
        else:
            # Calculate the distance between the two occurrences
            if (i - index[idx] - 1) != distance[idx]:
                return False  # If the distance does not match, return false
    
    return True  # All distances matched
← Back to All Questions