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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check Distances Between Same Letters

Number: 2476

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed string s where every letter appears exactly twice and an integer array distance of length 26 specifying the required number of letters between the two occurrences of each letter, determine if s is a well-spaced string. A string is well-spaced if for every letter that appears in s, the number of letters between its two occurrences is exactly as specified in the distance array (based on the letter's position in the alphabet). If a letter does not appear in s, its corresponding distance value can be ignored.

Key Insights

  • Each letter appears exactly twice, so we only need to record the indices of the first and second occurrences.
  • For a given letter, the distance between the two occurrences is calculated as (second_index - first_index - 1).
  • Convert the letter to its respective index (0 for 'a', 1 for 'b', etc.) to look up the expected distance from the distance array.
  • The string length is small (at most 52) so a simple linear scan with O(n) time complexity is sufficient.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s.
Space Complexity: O(1) (or O(26) for the dictionary), since the number of unique characters is bounded by 26.

Solution

We iterate through the string while keeping track of the first occurrence of each letter using a hash table. When we encounter a letter for the second time, we compute the number of letters between its two positions and compare this value with the expected distance from the distance array. If any letter does not satisfy the required spacing, we immediately return false. If all letters meet the condition, the string is well-spaced and we return true.

Code Solutions

# Python solution
def checkDistances(s, distance):
    # Dictionary to store the first index of each character.
    first_occurrence = {}
    
    # Loop over each character in the string along with its index.
    for index, char in enumerate(s):
        # Convert character to its corresponding index (0 for 'a', 1 for 'b', etc.)
        char_index = ord(char) - ord('a')
        
        # If we have already seen the character, check for the correct distance.
        if char in first_occurrence:
            # Calculate the gap between the two occurrences.
            gap = index - first_occurrence[char] - 1
            # If the gap does not match the required distance, return False.
            if gap != distance[char_index]:
                return False
        else:
            # Mark the current index as the first occurrence of the character.
            first_occurrence[char] = index
            
    # If all characters satisfy the distance condition, return True.
    return True

# Example usage:
# s = "abaccb", distance = [1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
# print(checkDistances(s, distance))  # Output: True
← Back to All Questions