Odd String Difference - Practice Coding Problems

Odd String Difference - Problem

You are given an array of equal-length strings words. Assume that the length of each string is n.

Each string words[i] can be converted into a difference integer array difference[i] of length n - 1 where difference[i][j] = words[i][j+1] - words[i][j] where 0 <= j <= n - 2. Note that the difference between two letters is the difference between their positions in the alphabet i.e. the position of 'a' is 0, 'b' is 1, and 'z' is 25.

For example, for the string "acb", the difference integer array is [2 - 0, 1 - 2] = [2, -1].

All the strings in words have the same difference integer array, except one. You should find that string.

Return the string in words that has different difference integer array.

Input & Output

Example 1 — Basic Case

$ Input: words = ["abc", "bcd", "acb"]

› Output: "acb"

💡 Note: "abc" → [1,1] (b-a=1, c-b=1), "bcd" → [1,1] (c-b=1, d-c=1), "acb" → [2,-1] (c-a=2, b-c=-1). The string "acb" has a different pattern.

Example 2 — Different Position

$ Input: words = ["adc", "wzy", "abc"]

› Output: "adc"

💡 Note: "adc" → [3,-1] (d-a=3, c-d=-1), "wzy" → [-3,1] (z-w=-3, y-z=1), "abc" → [1,1]. The string "adc" has a unique difference pattern.

Example 3 — Edge Case

$ Input: words = ["aaa", "bob", "ccc"]

› Output: "bob"

💡 Note: "aaa" → [0,0] (a-a=0, a-a=0), "bob" → [13,-13] (o-b=13, b-o=-13), "ccc" → [0,0]. The string "bob" is the only one with non-zero differences.

Constraints

3 ≤ words.length ≤ 100
n == words[i].length
2 ≤ n ≤ 20
words[i] consists of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Array of equal-length strings

Difference Arrays

Convert each string to consecutive character differences

Find Unique

Identify the string with different pattern

Key Takeaway

🎯 Key Insight: Only one string has a different consecutive character difference pattern - find it by comparing difference arrays efficiently.

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is that with exactly one odd string out, we only need to compare the first three strings to determine which pattern is unique. The optimal approach uses three-way comparison logic. Time: O(m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Comparison	O(n² × m)	O(n × m)	Compare each string's difference array with all others
Three-Way Comparison	O(m)	O(m)	Compare first three strings to identify the odd one efficiently
Frequency Count	O(n × m)	O(n × m)	Count occurrences of each difference pattern

Brute Force Comparison — Algorithm Steps

Convert each string to difference array
For each string, compare with all others
Return the string that has no matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to Arrays

Transform each string to difference array

Compare Pairs

Check each array against all others

Find Unique

Identify the array with no matches

Code -

solution.c — C

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

char* solution(char** words, int wordsSize) {
    if (wordsSize == 0) return "";
    
    int wordLen = strlen(words[0]);
    int diffLen = wordLen - 1;
    
    // Convert all words to difference arrays
    int** diffArrays = (int**)malloc(wordsSize * sizeof(int*));
    for (int i = 0; i < wordsSize; i++) {
        diffArrays[i] = (int*)malloc(diffLen * sizeof(int));
        for (int j = 0; j < diffLen; j++) {
            diffArrays[i][j] = words[i][j + 1] - words[i][j];
        }
    }
    
    // Find the unique one
    for (int i = 0; i < wordsSize; i++) {
        int isUnique = 1;
        for (int j = 0; j < wordsSize; j++) {
            if (i != j) {
                int same = 1;
                for (int k = 0; k < diffLen; k++) {
                    if (diffArrays[i][k] != diffArrays[j][k]) {
                        same = 0;
                        break;
                    }
                }
                if (same) {
                    isUnique = 0;
                    break;
                }
            }
        }
        if (isUnique) {
            // Free memory
            for (int x = 0; x < wordsSize; x++) {
                free(diffArrays[x]);
            }
            free(diffArrays);
            return words[i];
        }
    }
    
    // Free memory
    for (int i = 0; i < wordsSize; i++) {
        free(diffArrays[i]);
    }
    free(diffArrays);
    return "";
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for the contest format
    char** words = (char**)malloc(100 * sizeof(char*));
    int count = 0;
    
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        int len = strlen(token);
        while (len > 0 && (token[len-1] == ' ' || token[len-1] == '"')) len--;
        token[len] = '\0';
        
        words[count] = (char*)malloc(50 * sizeof(char));
        strcpy(words[count], token);
        count++;
        token = strtok(NULL, ",]");
    }
    
    char* result = solution(words, count);
    printf("%s\n", result);
    
    for (int i = 0; i < count; i++) {
        free(words[i]);
    }
    free(words);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

n² comparisons between strings, each taking O(m) time where m is string length

⚠ Quadratic Growth

Space Complexity

O(n × m)

Store difference arrays for all n strings, each of length m-1

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~12 min Avg. Time

245 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

Brute Force Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler