Shortest Uncommon Substring in an Array - Practice Coding Problems

Shortest Uncommon Substring in an Array - Problem

You are given an array arr of size n consisting of non-empty strings.

Find a string array answer of size n such that:

answer[i] is the shortest substring of arr[i] that does not occur as a substring in any other string in arr.
If multiple such substrings exist, answer[i] should be the lexicographically smallest.
If no such substring exists, answer[i] should be an empty string.

Return the array answer.

Input & Output

Example 1 — Basic Case

$ Input: arr = ["cab","ad","bad","c"]

› Output: ["ab","","ba",""]

💡 Note: For "cab": "c" appears in "c", "a" appears in "ad" and "bad", "b" appears in "bad", "ca" appears in none, "ab" appears in none (shorter), so "ab". For "ad": "a" appears in "cab" and "bad", "d" appears in "bad", "ad" appears in none but "ad" is the whole string and since we need shortest, we check if any single char works first - none do, so "ad" is not valid as there might be shorter ones. Actually "d" only appears in "bad" and "ad", but "d" appears in "bad" so it's not unique to "ad". Since no substring of "ad" is unique to "ad" only, return empty string.

Example 2 — Single Characters

$ Input: arr = ["abc","bcd","abcd"]

› Output: ["a","d","b"]

💡 Note: For "abc": "a" doesn't appear in "bcd" or "abcd" (wait, "a" appears in "abcd"), so "a" is not unique. Actually "a" appears in "abcd", "b" appears in "bcd" and "abcd", "c" appears in "bcd" and "abcd". Let's check "ab": appears in "abcd". "bc" appears in "bcd" and "abcd". "abc" appears in "abcd". So "abc" has no unique substring - return empty. Wait, let me recalculate: "a" appears in arr[0] and arr[2], "b" appears in all three, "c" appears in all three, "d" appears in arr[1] and arr[2]. So "a" appears in positions 0,2 so count=2. "d" appears in positions 1,2 so count=2. For "abc", we need substring that appears only in "abc" - none of single chars work, let's try "ab" - appears in "abc" and "abcd", so count=2. No unique substring exists for "abc".

Example 3 — Edge Case

$ Input: arr = ["a","aa","aaa"]

› Output: ["","aa","aaa"]

💡 Note: For "a": "a" appears in all strings, so no unique substring exists. For "aa": "a" appears in all, "aa" appears only in "aa" and "aaa", so count=2, not unique. Actually "aa" as substring appears in "aa" (the whole string) and "aaa" (as substring), so not unique to "aa". Wait, this seems wrong. Let me reconsider: "aa" the whole string is same as "aa" substring of "aaa", so "aa" appears in 2 strings. For "aaa": "aaa" appears only in "aaa", so it's unique.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings: ["cab", "ad", "bad", "c"]

Process

For each string, find shortest substring not in others

Output

Array of unique substrings: ["ab", "ad", "ba", "c"]

Key Takeaway

🎯 Key Insight: Generate substrings by increasing length and find the first one that's unique to each string

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to systematically check substrings by increasing length and find the first unique one. The optimal approach uses a hash map to precompute all substring counts, then searches for the shortest lexicographically smallest substring with count=1. Time: O(n × m³), Space: O(n × m²).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n × m³)	O(n × m²)	Use hash map to precompute all substrings and their counts for efficient lookup
Brute Force - Check All Substrings	O(n² × m³)	O(m)	Generate all substrings for each string and check uniqueness by searching other strings

Hash Map Optimization — Algorithm Steps

Step 1: Generate all substrings from all strings and count occurrences in hash map
Step 2: For each string, iterate through substrings by length
Step 3: Return first substring with count = 1 in hash map

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Phase

Build hash map of all substring occurrences

Search Phase

Find shortest substring with count = 1

Result

Return lexicographically smallest unique substring

Code -

solution.c — C

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

#define MAX_SUBSTRINGS 10000

typedef struct {
    char str[101];
    int count;
} SubstringCount;

SubstringCount substringMap[MAX_SUBSTRINGS];
int mapSize = 0;

int findSubstring(char* substring) {
    for (int i = 0; i < mapSize; i++) {
        if (strcmp(substringMap[i].str, substring) == 0) {
            return i;
        }
    }
    return -1;
}

void addSubstring(char* substring) {
    int index = findSubstring(substring);
    if (index >= 0) {
        substringMap[index].count++;
    } else {
        strcpy(substringMap[mapSize].str, substring);
        substringMap[mapSize].count = 1;
        mapSize++;
    }
}

char** solution(char** arr, int n, int* returnSize) {
    mapSize = 0;
    char** result = (char**)malloc(n * sizeof(char*));
    *returnSize = n;
    
    // First pass: count all substrings
    for (int i = 0; i < n; i++) {
        char* s = arr[i];
        int len = strlen(s);
        char seen[1000][101];
        int seenCount = 0;
        
        for (int start = 0; start < len; start++) {
            for (int end = start + 1; end <= len; end++) {
                char substring[101];
                strncpy(substring, s + start, end - start);
                substring[end - start] = '\0';
                
                // Check if already seen for this string
                int alreadySeen = 0;
                for (int k = 0; k < seenCount; k++) {
                    if (strcmp(seen[k], substring) == 0) {
                        alreadySeen = 1;
                        break;
                    }
                }
                
                if (!alreadySeen) {
                    strcpy(seen[seenCount], substring);
                    seenCount++;
                    addSubstring(substring);
                }
            }
        }
    }
    
    // Second pass: find shortest unique substring for each string
    for (int i = 0; i < n; i++) {
        char* current = arr[i];
        int currentLen = strlen(current);
        int found = 0;
        result[i] = (char*)malloc(101 * sizeof(char));
        result[i][0] = '\0';
        
        // Try substrings of increasing length
        for (int length = 1; length <= currentLen && !found; length++) {
            char candidates[100][101];
            int candidateCount = 0;
            
            // Generate all substrings of current length
            for (int start = 0; start <= currentLen - length; start++) {
                char substring[101];
                strncpy(substring, current + start, length);
                substring[length] = '\0';
                
                int index = findSubstring(substring);
                if (index >= 0 && substringMap[index].count == 1) {
                    strcpy(candidates[candidateCount], substring);
                    candidateCount++;
                }
            }
            
            // If we found unique substrings of this length, take lexicographically smallest
            if (candidateCount > 0) {
                strcpy(result[i], candidates[0]);
                for (int k = 1; k < candidateCount; k++) {
                    if (strcmp(candidates[k], result[i]) < 0) {
                        strcpy(result[i], candidates[k]);
                    }
                }
                found = 1;
            }
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for demo
    char* arr[10];
    int n = 0;
    
    // Parse basic array format
    char* token = strtok(line, "[],\"");
    while (token != NULL && n < 10) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            arr[n] = (char*)malloc(strlen(token) + 1);
            strcpy(arr[n], token);
            n++;
        }
        token = strtok(NULL, "[],\"");
    }
    
    int returnSize;
    char** result = solution(arr, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m³)

Generate O(m²) substrings for each of n strings, hash operations are O(1)

✓ Linear Growth

Space Complexity

O(n × m²)

Hash map stores all unique substrings from all strings

⚡ Linearithmic Space

2.2K Views

Medium Frequency

~25 min Avg. Time

89 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 Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler