Challenge
Challenge
Problem
Solutions
Submissions
Challenge Points: 30
Level: HardYou are given a square matrix lcp of size n × n.
This matrix describes how similar the suffixes of a string should be.
Imagine we have a string word of length n made of lowercase English letters.
lcp[i][j] tells how many characters match from the start when comparing:
the suffix beginning at i: word[i ... n-1]
the suffix beginning at j: word[j ... n-1]
Your task is to construct the lexicographically smallest string that matches the given lcp matrix.
If no such string is possible, return an empty string.
Input: lcp = [ [3,1,0], [1,2,0], [0,0,1] ]
Output: "aab"
Explanation:
The matrix describes prefix matches between suffixes. The smallest valid word is "aba".
Input: lcp = [ [2,0], [0,1] ]
Output: "ab"
Explanation:
Only one character is needed to satisfy all prefix constraints.
Input: lcp = [ [3,2,1], [2,2,1], [1,1,1] ]
Output: "aaa"
Explanation:
This matrix implies impossible prefix rules. So no valid string exists.
Accepted:
Submission:
Report an issue
Code
You need toto run or submitYou need toto run or submit
Test Case
Test Result