Strings Differ by One Character - Practice Coding Problems

Strings Differ by One Character - Problem

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.

Note: Two strings differ by one character means exactly one position has different characters while all other positions have the same character.

Input & Output

Example 1 — Basic Case

$ Input: dict = ["abcd","acbd","aacd"]

› Output: true

💡 Note: Strings "abcd" and "aacd" differ by exactly 1 character at index 1 (b vs a)

Example 2 — No Match

$ Input: dict = ["ab","cd","yz"]

› Output: false

💡 Note: No two strings differ by exactly 1 character. Each pair differs by 2 characters

Example 3 — Multiple Differences

$ Input: dict = ["abcd","cccc","abcy","abcde"]

› Output: true

💡 Note: Strings "abcd" and "abcy" differ by exactly 1 character at index 3 (d vs y)

Constraints

1 ≤ dict.length ≤ 10⁵
1 ≤ dict[i].length ≤ 20
dict[i] consists of lowercase English letters only
All strings in dict have the same length

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings with same length

Process

Find pairs differing by exactly 1 character

Output

Return true if such pair exists

Key Takeaway

🎯 Key Insight: Generate patterns by masking each position to efficiently find string pairs that differ by exactly one character

Asked in

G Google 35 f Facebook 28 a Amazon 22

The key insight is to use pattern matching by generating masks for each character position. The hash map approach is optimal with O(n×m²) time complexity by creating patterns like "ab*" and detecting duplicates.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Patterns	O(n × m²)	O(n × m²)	Generate patterns by masking each position and use hash map to find matches
Brute Force Comparison	O(n² × m)	O(1)	Compare every pair of strings and count character differences

Hash Map with Patterns — Algorithm Steps

For each string, create patterns by masking each position
Store patterns in hash map
If pattern already exists, return true

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Patterns

Create patterns by masking each position

Check Hash Map

Look for duplicate patterns

Match Found

Return true when pattern already exists

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_PATTERNS 10000

bool solution(char dict[][100], int n, int len) {
    char patterns[MAX_PATTERNS][100];
    int patternCount = 0;
    
    for (int w = 0; w < n; w++) {
        for (int i = 0; i < len; i++) {
            char pattern[100];
            strncpy(pattern, dict[w], i);
            pattern[i] = '*';
            strcpy(pattern + i + 1, dict[w] + i + 1);
            
            for (int p = 0; p < patternCount; p++) {
                if (strcmp(patterns[p], pattern) == 0) {
                    return true;
                }
            }
            strcpy(patterns[patternCount++], pattern);
        }
    }
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    char dict[100][100];
    int n = 0, len = 0;
    char *token = strtok(line, "[],\" \n");
    while (token != NULL && n < 100) {
        strcpy(dict[n], token);
        if (len == 0) len = strlen(token);
        n++;
        token = strtok(NULL, "[],\" \n");
    }
    printf(solution(dict, n, len) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m²)

For each of n strings, generate m patterns of length m

✓ Linear Growth

Space Complexity

O(n × m²)

Hash map stores up to n×m patterns, each of length m

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map with Patterns — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler