Find the String with LCP - Practice Coding Problems

Find the String with LCP - Problem

Array String Dynamic Programming Greedy Union Find Matrix Hard

We define the lcp matrix of any 0-indexed string word of n lowercase English letters as an n x n grid such that:

lcp[i][j] is equal to the length of the longest common prefix between the substrings word[i,n-1] and word[j,n-1].

Given an n x n matrix lcp, return the alphabetically smallest string word that corresponds to lcp. If there is no such string, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Input & Output

Example 1 — Basic Case

$ Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]

› Output: abab

💡 Note: The LCP matrix corresponds to the string 'abab'. lcp[0][2] = 2 because substrings 'abab' and 'ab' share 'ab' as prefix.

Example 2 — Single Character

$ Input: lcp = [[1]]

› Output: a

💡 Note: For a single character, lcp[0][0] = 1 means the suffix has length 1, so the string is 'a'.

Example 3 — Impossible Case

$ Input: lcp = [[3,3],[3,3]]

› Output:

💡 Note: This matrix is impossible because lcp[0][1] = 3 but there are only 2 characters, so max LCP should be 2.

Constraints

1 ≤ lcp.length ≤ 1000
lcp[i].length == lcp.length
0 ≤ lcp[i][j] ≤ lcp.length

Visualization

Tap to expand

Understanding the Visualization

Input

LCP matrix showing longest common prefixes between suffixes

Process

Build string character by character using constraints

Output

Lexicographically smallest string that produces the LCP matrix

Key Takeaway

🎯 Key Insight: Use LCP constraints to guide greedy character selection, ensuring the lexicographically smallest valid string

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use the LCP matrix constraints to build the string greedily, choosing the lexicographically smallest valid character at each position. The greedy approach ensures we get the smallest possible string while satisfying all LCP requirements. Time: O(n² × 26), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Character Construction	O(n² × 26)	O(n²)	Build the string character by character, choosing the smallest valid letter at each position
Brute Force - Try All Strings	O(26ⁿ × n³)	O(n²)	Generate all possible strings and check which one produces the given LCP matrix

Greedy Character Construction — Algorithm Steps

Start with empty string
For each position, try characters 'a' to 'z'
Check if placing this character satisfies LCP constraints
Choose the first valid character (lexicographically smallest)
Continue until string is complete

Visualization

Tap to expand

Step-by-Step Walkthrough

Position 0

Try 'a', check if it satisfies LCP constraints

Position 1

Try 'a', then 'b', until we find valid character

Continue

Build rest of string greedily

Code -

solution.c — C

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

char* solution(int** lcp, int n) {
    if (n == 0) {
        char* empty = malloc(1);
        empty[0] = '\0';
        return empty;
    }
    
    // Validate LCP matrix
    for (int i = 0; i < n; i++) {
        if (lcp[i][i] != n - i) {
            char* empty = malloc(1);
            empty[0] = '\0';
            return empty;
        }
        for (int j = 0; j < n; j++) {
            if (lcp[i][j] != lcp[j][i]) {
                char* empty = malloc(1);
                empty[0] = '\0';
                return empty;
            }
            int max = (i > j) ? i : j;
            if (lcp[i][j] > n - max) {
                char* empty = malloc(1);
                empty[0] = '\0';
                return empty;
            }
        }
    }
    
    char* result = malloc((n + 1) * sizeof(char));
    result[n] = '\0';
    
    for (int pos = 0; pos < n; pos++) {
        int found = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            result[pos] = c;
            int valid = 1;
            
            for (int prev = 0; prev < pos && valid; prev++) {
                int k = 0;
                while (prev + k <= pos && result[prev + k] == result[pos + k]) {
                    k++;
                }
                
                if (pos + k < n) {
                    if (k > lcp[prev][pos]) {
                        valid = 0;
                    }
                } else {
                    if (k != lcp[prev][pos]) {
                        valid = 0;
                    }
                }
            }
            
            if (valid) {
                found = 1;
                break;
            }
        }
        if (!found) {
            free(result);
            char* empty = malloc(1);
            empty[0] = '\0';
            return empty;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for demonstration
    int n = 2; // Default small case
    int** lcp = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        lcp[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            lcp[i][j] = (i == j) ? n - i : 0;
        }
    }
    
    char* result = solution(lcp, n);
    printf("%s\n", result);
    
    for (int i = 0; i < n; i++) free(lcp[i]);
    free(lcp);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × 26)

For each of n positions, try 26 characters, each requiring O(n) constraint checks

⚠ Quadratic Growth

Space Complexity

O(n²)

Space to store the result string and validate constraints against the LCP matrix

⚠ Quadratic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

234 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

Greedy Character Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler