Find the String with LCP

Problem

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. For example, "aabd" is lexicographically smaller than "aaca" because the first position they differ is at the third letter, and 'b' comes before 'c'.

Examples

Example 1

1
2
3


Input: lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
Output: "abab"
Explanation: lcp corresponds to any 4 letter string with two alternating letters. The lexicographically smallest of them is "abab".

Example 2

1
2
3


Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
Output: "aaaa"
Explanation: lcp corresponds to any 4 letter string with a single distinct letter. The lexicographically smallest of them is "aaaa". 

Example 3

1
2
3


Input: lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
Output: ""
Explanation: lcp[3][3] cannot be equal to 3 since word[3,...,3] consists of only a single letter; Thus, no answer exists.

Constraints

1 <= n == ``lcp.length == ``lcp[i].length <= 1000
0 <= lcp[i][j] <= n

Solution

Method 1 – Greedy + Union-Find

Intuition

We want to construct the lexicographically smallest string that matches the given LCP matrix. If lcp[i][j] > 0, then word[i] == word[j]. We can use union-find to group indices that must have the same character. Then, assign the smallest possible character to each group, and check if the constructed string matches the LCP matrix.

Approach

Use union-find to group indices i, j where lcp[i][j] > 0.
Assign the smallest available character to each group, in order.
Build the string by assigning each index the character of its group.
Check if the constructed string’s LCP matrix matches the input. If not, return an empty string.
Return the constructed string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution {
public:
    string findTheString(vector<vector<int>>& lcp) {
        int n = lcp.size();
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        function<int(int)> find = [&](int x) { return p[x] == x ? x : p[x] = find(p[x]); };
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (lcp[i][j] > 0) p[find(i)] = find(j);
            }
        }
        vector<int> group(n);
        int gid = 0;
        unordered_map<int, char> g2c;
        for (int i = 0; i < n; ++i) {
            int root = find(i);
            if (!g2c.count(root)) g2c[root] = 'a' + gid++;
            if (gid > 26) return "";
            group[i] = root;
        }
        string ans(n, ' ');
        for (int i = 0; i < n; ++i) ans[i] = g2c[find(i)];
        // Validate
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int len = 0;
                while (i + len < n && j + len < n && ans[i + len] == ans[j + len]) ++len;
                if (lcp[i][j] != len) return "";
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


func findTheString(lcp [][]int) string {
    n := len(lcp)
    p := make([]int, n)
    for i := range p { p[i] = i }
    var find func(int) int
    find = func(x int) int {
        if p[x] != x { p[x] = find(p[x]) }
        return p[x]
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if lcp[i][j] > 0 {
                p[find(i)] = find(j)
            }
        }
    }
    g2c := map[int]byte{}
    gid := 0
    ans := make([]byte, n)
    for i := 0; i < n; i++ {
        root := find(i)
        if _, ok := g2c[root]; !ok {
            if gid >= 26 { return "" }
            g2c[root] = byte('a' + gid)
            gid++
        }
        ans[i] = g2c[root]
    }
    // Validate
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            l := 0
            for i+l < n && j+l < n && ans[i+l] == ans[j+l] { l++ }
            if lcp[i][j] != l { return "" }
        }
    }
    return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
    public String findTheString(int[][] lcp) {
        int n = lcp.length;
        int[] p = new int[n];
        for (int i = 0; i < n; ++i) p[i] = i;
        java.util.function.IntUnaryOperator find = new java.util.function.IntUnaryOperator() {
            public int applyAsInt(int x) { return p[x] == x ? x : (p[x] = applyAsInt(p[x])); }
        };
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (lcp[i][j] > 0) p[find.applyAsInt(i)] = find.applyAsInt(j);
            }
        }
        Map<Integer, Character> g2c = new HashMap<>();
        int gid = 0;
        char[] ans = new char[n];
        for (int i = 0; i < n; ++i) {
            int root = find.applyAsInt(i);
            if (!g2c.containsKey(root)) {
                if (gid >= 26) return "";
                g2c.put(root, (char)('a' + gid++));
            }
            ans[i] = g2c.get(root);
        }
        // Validate
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int l = 0;
                while (i + l < n && j + l < n && ans[i + l] == ans[j + l]) l++;
                if (lcp[i][j] != l) return "";
            }
        }
        return new String(ans);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
    fun findTheString(lcp: Array<IntArray>): String {
        val n = lcp.size
        val p = IntArray(n) { it }
        fun find(x: Int): Int {
            if (p[x] != x) p[x] = find(p[x])
            return p[x]
        }
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (lcp[i][j] > 0) p[find(i)] = find(j)
            }
        }
        val g2c = mutableMapOf<Int, Char>()
        var gid = 0
        val ans = CharArray(n)
        for (i in 0 until n) {
            val root = find(i)
            if (g2c[root] == null) {
                if (gid >= 26) return ""
                g2c[root] = ('a' + gid++)
            }
            ans[i] = g2c[root]!!
        }
        // Validate
        for (i in 0 until n) {
            for (j in 0 until n) {
                var l = 0
                while (i + l < n && j + l < n && ans[i + l] == ans[j + l]) l++
                if (lcp[i][j] != l) return ""
            }
        }
        return String(ans)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution:
    def findTheString(self, lcp: list[list[int]]) -> str:
        n = len(lcp)
        p = list(range(n))
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]
        for i in range(n):
            for j in range(n):
                if lcp[i][j] > 0:
                    p[find(i)] = find(j)
        g2c = {}
        gid = 0
        ans = [''] * n
        for i in range(n):
            root = find(i)
            if root not in g2c:
                if gid >= 26:
                    return ''
                g2c[root] = chr(ord('a') + gid)
                gid += 1
            ans[i] = g2c[root]
        # Validate
        for i in range(n):
            for j in range(n):
                l = 0
                while i + l < n and j + l < n and ans[i + l] == ans[j + l]:
                    l += 1
                if lcp[i][j] != l:
                    return ''
        return ''.join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


impl Solution {
    pub fn find_the_string(lcp: Vec<Vec<i32>>) -> String {
        let n = lcp.len();
        let mut p: Vec<usize> = (0..n).collect();
        fn find(p: &mut Vec<usize>, x: usize) -> usize {
            if p[x] != x { p[x] = find(p, p[x]); }
            p[x]
        }
        for i in 0..n {
            for j in 0..n {
                if lcp[i][j] > 0 {
                    let a = find(&mut p, i);
                    let b = find(&mut p, j);
                    p[a] = b;
                }
            }
        }
        let mut g2c = std::collections::HashMap::new();
        let mut gid = 0;
        let mut ans = vec!['a'; n];
        for i in 0..n {
            let root = find(&mut p, i);
            if !g2c.contains_key(&root) {
                if gid >= 26 { return String::new(); }
                g2c.insert(root, (b'a' + gid) as char);
                gid += 1;
            }
            ans[i] = *g2c.get(&root).unwrap();
        }
        // Validate
        for i in 0..n {
            for j in 0..n {
                let mut l = 0;
                while i + l < n && j + l < n && ans[i + l] == ans[j + l] {
                    l += 1;
                }
                if lcp[i][j] != l as i32 {
                    return String::new();
                }
            }
        }
        ans.into_iter().collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    findTheString(lcp: number[][]): string {
        const n = lcp.length;
        const p = Array.from({length: n}, (_, i) => i);
        const find = (x: number): number => p[x] === x ? x : (p[x] = find(p[x]));
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                if (lcp[i][j] > 0) p[find(i)] = find(j);
            }
        }
        const g2c: Record<number, string> = {};
        let gid = 0;
        const ans: string[] = Array(n);
        for (let i = 0; i < n; ++i) {
            const root = find(i);
            if (!(root in g2c)) {
                if (gid >= 26) return '';
                g2c[root] = String.fromCharCode(97 + gid++);
            }
            ans[i] = g2c[root];
        }
        // Validate
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < n; ++j) {
                let l = 0;
                while (i + l < n && j + l < n && ans[i + l] === ans[j + l]) ++l;
                if (lcp[i][j] !== l) return '';
            }
        }
        return ans.join('');
    }
}

Complexity

⏰ Time complexity: O(n^3) — For union-find and validation.
🧺 Space complexity: O(n^2) — For the LCP matrix and auxiliary structures.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Greedy + Union-Find#

Intuition#

Approach#

Code#

Complexity#