We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the String with LCP

Number: 2708

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an n x n lcp matrix, where lcp[i][j] equals the length of the longest common prefix between the suffixes word[i:] and word[j:], return the lexicographically smallest string "word" (composed of lowercase English letters) that produces this matrix. If no such word exists, return an empty string.

Key Insights

  • The diagonal lcp[i][i] must equal the length of the suffix starting at i (i.e. n - i).
  • A positive lcp[i][j] implies that the first character of word[i] and word[j] must be the same.
  • Characters at positions beyond the common prefix must differ if the lcp value is less than the available length.
  • The constraints imply equality relationships between different positions that can be captured using union-find.
  • To achieve the lexicographically smallest result, assign the smallest possible available letter to each equivalence class.
  • After constructing a candidate string, validate it against the provided lcp matrix.

Space and Time Complexity

Time Complexity: O(n^2) due to the nested loops for unioning, grouping, and validating the lcp for each pair. Space Complexity: O(n) for the union-find structure, with additional O(n^2) for iterating over the lcp matrix in the worst-case.

Solution

We first validate the diagonal conditions (i.e. lcp[i][i] == n - i). Then, using a union-find (disjoint set) structure, we union indices that must carry the same character when lcp[i][j] > 0. After forming these groups, we ensure that the number of distinct groups does not exceed 26 (the total number of lowercase letters). We then assign letters to each group in order of their smallest index to achieve the lexicographically smallest answer. Finally, we validate that the constructed candidate string matches the lcp matrix, returning the string if valid, or an empty string otherwise.

Code Solutions

def findTheString(lcp):
    n = len(lcp)
    # Check diagonal constraint: lcp[i][i] must equal n - i.
    for i in range(n):
        if lcp[i][i] != n - i:
            return ""
    
    # Initialize union-find structure.
    parent = list(range(n))
    def find(a):
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra

    # Union positions that must share the same character.
    for i in range(n):
        for j in range(i + 1, n):
            if lcp[i][j] > 0:
                union(i, j)
    
    # Group indices by their representative.
    groups = {}
    for i in range(n):
        root = find(i)
        groups.setdefault(root, []).append(i)
    
    # More than 26 distinct groups means not enough letters.
    if len(groups) > 26:
        return ""
    
    # Greedily assign the smallest letters based on the smallest index in the group.
    ans = [''] * n
    orderedGroups = sorted(groups.items(), key=lambda x: min(x[1]))
    current_letter = ord('a')
    for _, indices in orderedGroups:
        for i in indices:
            ans[i] = chr(current_letter)
        current_letter += 1
    
    candidate = "".join(ans)
    
    # Validate candidate string with the given lcp matrix.
    def calc_lcp(i, j):
        count = 0
        while i < n and j < n and candidate[i] == candidate[j]:
            count += 1
            i += 1
            j += 1
        return count
    
    for i in range(n):
        for j in range(n):
            if calc_lcp(i, j) != lcp[i][j]:
                return ""
    return candidate

# Example test case:
print(findTheString([[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]))  # Expected output "abab"
← Back to All Questions