Is Strings Differ by One Character easy or hard?

Strings Differ by One Character is typically rated Medium. The brute force idea is straightforward, but recognizing that hashing can avoid pairwise comparisons requires deeper algorithmic thinking.

Strings Differ by One Character Python/Java solution

Most implementations use rolling hash with a set. Python, Java, C++, and Go versions compute hashes for each string and adjust them when removing a character index. The logic remains the same across languages with minor differences in hash arithmetic and data structures.

How to solve Strings Differ by One Character in O(n*m)?

Compute a rolling hash for every string and precompute base powers. For each character index, subtract that character's hash contribution to simulate removing it. Insert the resulting hash into a set and check for duplicates. If two hashes match at the same removed index, the strings differ by exactly one character.

What is the best approach for Strings Differ by One Character?

The optimal approach uses rolling hash and a hash set. Compute a polynomial hash for each string, then remove the contribution of each character position and check if the resulting hash already exists. This reduces comparisons and runs in O(n * m) time with O(n) extra space.

Is Strings Differ by One Character asked at Google/Amazon/Meta?

This problem reflects common interview patterns used by large tech companies. Variations involving hashing, string comparison, and detecting near-duplicates appear in interviews at companies like Google, Amazon, and Meta because they test hashing and optimization skills.

What data structure is used in Strings Differ by One Character?

A hash set is the key data structure. It stores modified string hashes or substrings generated after removing one character position. Hash lookups allow constant-time duplicate detection, which avoids quadratic pair comparisons.

What is the time complexity of Strings Differ by One Character?

The optimal rolling hash solution runs in O(n * m) time where n is the number of strings and m is the length of each string. Each position is processed once for all strings. Space complexity is O(n) due to storing intermediate hashes in a set.

Description Hints 2 Solution Video 7:25

1554. Strings Differ by One Character

Medium39.4% acceptance1 companyPremium elsewhere, free here

Given a list of strings dict where all the strings are of the same length.

Return true if there are 2 strings that only differ by 1 character in the same index, otherwise return false.

Example 1:

Input: dict = ["abcd","acbd", "aacd"]
Output: true
Explanation: Strings "abcd" and "aacd" differ only by one character in the index 1.

Example 2:

Input: dict = ["ab","cd","yz"]
Output: false

Example 3:

Input: dict = ["abcd","cccc","abyd","abab"]
Output: true

Constraints:

The number of characters in dict <= 10⁵
dict[i].length == dict[j].length
dict[i] should be unique.
dict[i] contains only lowercase English letters.

Asked at 1 company

Airbnb

Topics

Hints open one at a time

Hint 1

BruteForce, check all pairs and verify if they differ in one character. O(n^2 * m) where n is the number of words and m is the length of each string.

Hint 2

O(m^2 * n), Use hashset, to insert all possible combinations adding a character "*". For example: If dict[i] = "abc", insert ("*bc", "a*c" and "ab*").

7:25

Still stuck?Read the written solution, or watch a walkthrough.

Open solution