Skip to main content
Talentd

Strings Differ by One Character - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringRolling HashHash Function4 min readAsked at: Airbnb
Practice this problem

Problem Statement

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 <= 105
  • dict[i].length == dict[j].length
  • dict[i] should be unique.
  • dict[i] contains only lowercase English letters.

Approach Overview

Problem Overview: You receive an array of equal-length strings. The task is to determine whether any two strings differ by exactly one character at the same index. If such a pair exists, return true. Otherwise return false.

Approach 1: Pairwise Comparison (Brute Force) (O(n² * m) time, O(1) space)

Compare every pair of strings and count how many positions differ. For each pair, iterate through all m characters and increment a mismatch counter. If the count equals one, the condition is satisfied and you return true. This approach is simple but expensive because it performs comparisons across all n² pairs and scans each string fully.

Approach 2: Hashing by Removing One Character (O(n * m) time, O(n) space)

Instead of comparing every pair, iterate through each character index and simulate removing that position from every string. Build a modified version of each string that skips the current index. Store these modified strings in a HashSet. If two strings become identical after removing the same index, they must differ by exactly one character at that position. This reduces pairwise comparisons and leverages fast hash lookups. The approach relies heavily on efficient Hash Table operations and string processing.

Approach 3: Rolling Hash with Character Removal (Optimal) (O(n * m) time, O(n) space)

Instead of rebuilding strings, compute a polynomial rolling hash for each string. Precompute powers for the hash base. For every index i, adjust each string's hash by subtracting the contribution of the character at position i. The resulting hash represents the string with that character removed. Insert these hashes into a set and check for duplicates. Hash comparison avoids constructing new strings, which improves constant factors and memory behavior. This technique combines string manipulation with rolling hash techniques used in substring matching algorithms.

Recommended for interviews: The rolling hash solution is the expected optimal approach because it reduces the naive quadratic comparison into linear passes over the data. Showing the brute force approach first demonstrates understanding of the requirement, but implementing the hash-based method shows stronger algorithmic reasoning and familiarity with hashing optimizations.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pairwise Comparison (Brute Force)O(n² * m)O(1)Small datasets or when implementing the simplest correctness check
Hashing by Removing One CharacterO(n * m)O(n)When string reconstruction cost is acceptable and implementation simplicity is preferred
Rolling Hash Character RemovalO(n * m)O(n)Best general solution with efficient hashing and minimal string copying

Video Solution

1554. Strings Differ by One Character • Muerde un zombie • 1,515 views views

Watch 1 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Strings Differ by One Character with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Words Obtained After Adding a Letter