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

Strings Differ by One Character

Number: 1697

Difficulty: Medium

Paid? Yes

Companies: Okta, Airbnb

Problem Description

Given a list of strings dict where all the strings are of the same length, return true if there are 2 strings that differ by exactly one character in the same index, otherwise return false.

Key Insights

  • All strings have the same fixed length, which allows uniform processing.
  • By “masking” one character at a time (e.g., by replacing it with a placeholder such as "*"), you can capture the string with one character removed.
  • If two strings differ by only one character, they will share the same masked pattern at the differing index.
  • A hash set (or hash table) can store these masked patterns to enable O(1) average lookup.
  • Iterating through each string and each character position gives an overall time complexity of O(n * m).

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of strings and m is the length of each string.
Space Complexity: O(n * m), for storing the masked versions in the hash set.

Solution

For each string, iterate over every character position and create a masked version of the string by replacing the character at that position with a wildcard (e.g., "*"). Store these masked versions in a hash set. If the current masked version is already in the set, it means there exists another string that can form the same masked version (i.e., the two strings differ by exactly one character at that index), so return true immediately. If no matching masked string is found after processing all strings, return false.

Code Solutions

# Python solution with line-by-line comments
def differ_by_one(dict_strings):
    # Initialize hash set to store masked versions of strings
    seen = {}
    # Iterate through each string in the given list
    for s in dict_strings:
        # For every index in the string, create a masked version
        for i in range(len(s)):
            # Replace character at index i with a wildcard '*'
            key = s[:i] + "*" + s[i+1:]
            # If the masked version is already in the set, return True
            if key in seen:
                return True
            else:
                seen[key] = s
    # If no suitable pair found, return False
    return False

# Example usage:
print(differ_by_one(["abcd", "acbd", "aacd"]))  # Expected Output: True
print(differ_by_one(["ab", "cd", "yz"]))          # Expected Output: False
← Back to All Questions