Find the String with LCP — LeetCode 2573 Python Solution

The 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.

Example

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".

Python solution

class Solution:
    def findTheString(self, lcp: List[List[int]]) -> str:
        n = len(lcp)
        s = [""] * n
        i = 0
        for c in ascii_lowercase:
            while i < n and s[i]:
                i += 1
            if i == n:
                break
            for j in range(i, n):
                if lcp[i][j]:
                    s[j] = c
        if "" in s:
            return ""
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if s[i] == s[j]:
                    if i == n - 1 or j == n - 1:
                        if lcp[i][j] != 1:
                            return ""
                    elif lcp[i][j] != lcp[i + 1][j + 1] + 1:
                        return ""
                elif lcp[i][j]:
                    return ""
        return "".join(s)

Complexity

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2573. Find the String with LCP is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Related problems