algoadvance

Given a string s of lowercase English letters and an array of integers distance of length 26, where distance[i] represents the desired distance between the two occurrences of the i-th letter in the alphabet (0-indexed), return true if for every letter in s, the distance between the two occurrences of the letter is equal to the respective value in the distance array. Otherwise, return false.

Clarifying Questions

1. Q: What happens if a letter appears more than twice in the string?
   • A: The problem statement assumes each letter will appear exactly twice if it appears in the string.
2. Q: Can the string or distance array be empty?
   • A: The problem assumes that s and distance will have appropriate lengths as described in the problem constraints.

Strategy

1. Iterate over the string s and keep track of the first occurrence of each letter with the help of a dictionary.
2. Calculate the actual distance between two occurrences of each letter.
3. Compare this actual distance with the pre-specified distance in the distance array.

Code

Here’s the code implementing the strategy:

def checkDistances(s: str, distance: list[int]) -> bool:
    letter_pos = {}
    
    for idx, char in enumerate(s):
        if char in letter_pos:
            actual_distance = idx - letter_pos[char] - 1
            expected_distance = distance[ord(char) - ord('a')]
            if actual_distance != expected_distance:
                return False
        else:
            letter_pos[char] = idx
    
    return True

# Example usage:
s = "abaccb"
distance = [1, 2, 0, ...]  # for simplicity in this example
print(checkDistances(s, distance))  # Output should be True or False based on the distance array

Time Complexity

• Time Complexity: O(n), where n is the length of the string s. We scan through the string once and perform constant-time dictionary operations.
• Space Complexity: O(1), because the size of the dictionary is bounded by the number of lowercase English letters which is 26, so it’s constant space.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?