Explained | 4ms
IntuitionA two-phase approach to construct the alphabetically smallest string that satisfies the given LCP matrix, then validate it against LCP constraints.Appr
# Intuition
A two-phase approach to construct the alphabetically smallest string that satisfies the given LCP matrix, then validate it against LCP constraints.

# Approach
1. **Phase 1**: Construct string letter-by-letter
   - Reuse existing characters when LCP > 0 with previous indices
   - Assign the next alphabetically smallest letter when needed
   - Return empty if we exceed 26 letters

2. **Phase 2**: Validate the constructed string against LCP matrix
   - Verify LCP matrix symmetry
   - Check that characters match when LCP > 0
   - Validate recurrence relation: lcp[i+1][j+1] = lcp[i][j]-1
   - Ensure characters differ when LCP = 0
   - Handle boundary cases for last position

# Complexity
- Time complexity: O(n²) - we process each element of the n×n LCP matrix once

# Code
```cpp []
class Solution {
public:
    string findTheString(const vector<vector<int>>& lcp) {
        const int L = lcp.size();
        string res(L, 0); // '\0' means not yet defined.

        // PHASE 1: Construct the string based on LCP matrix constraints
        for (int i = 0, uch = 'a'; i < L; ++i) {
            if (lcp[i][i] != L - i) return ""; // Validate diagonal
            for (int j = 0; j < i; ++j)
                if (lcp[i][j])        // If they share any common prefix
                    res[i] = res[j];  // Use the same character as position j
            if (res[i]) continue;     // Skip if already assigned
            if (uch > 'z') return ""; // Return empty if we need more than 26 letters
            res[i] = uch++;           // Assign next available letter in alphabet
        }

        // PHASE 2: Verify the constructed string satisfies the given LCP matrix
        for (int i = 0; i < L; ++i) for (int j = i + 1; j < L; ++j) {
            if (lcp[i][j] != lcp[j][i]) return ""; // Check symmetry
            if (lcp[i][j]) {
                if (res[i] != res[j]) return ""; // If share common prefix => chars must be identical
                if (j < L - 1) {
                    // For non-last positions: verify LCP values follow the recurrence relation
                    if (lcp[i + 1][j + 1] != lcp[i][j] - 1) return "";
                } else if (lcp[i][j] > 1) return ""; // j == L-1 => CP can not exceed 1
            } else if (res[i] == res[j]) return "";  // If LCP is 0, characters must differ
        }

        return res;
    }
};

```
['C++']