C++ union find
\nclass Solution {\npublic:\n  vector<int> idxToParent;\n  vector<vector<bool>> eligible;\n  vector<char> parentToChar;\n  vector<unordered_set<int>> different;
```\nclass Solution {\npublic:\n  vector<int> idxToParent;\n  vector<vector<bool>> eligible;\n  vector<char> parentToChar;\n  vector<unordered_set<int>> different;\n\n  int getParent(int idx) {\n    if (idxToParent[idx] == -1) {\n      idxToParent[idx] = idx;\n    }\n    if (idxToParent[idx] == idx) {\n      return idx;\n    }\n    idxToParent[idx] = getParent(idxToParent[idx]);\n    return idxToParent[idx];\n  }\n  \n  bool combineParents(int idx1, int idx2) {\n    int parentIdx1 = getParent(idx1);\n    int parentIdx2 = getParent(idx2);\n    for (int i = 0; i < 26; ++i) {\n      if (eligible[parentIdx1][i] != eligible[parentIdx2][i]) {\n        return false;\n      }\n    }\n    if (different[parentIdx1].find(parentIdx2) != different[parentIdx1].end()) {\n      return false;\n    }\n    if (different[parentIdx2].find(parentIdx1) != different[parentIdx2].end()) {\n      return false;\n    }\n    for (auto it = different[parentIdx2].begin();\n        it != different[parentIdx2].end();\n        ++it) {\n      different[parentIdx1].insert(*it);\n    }\n    idxToParent[parentIdx2] = parentIdx1;\n    return true;\n  }\n  \n  bool tryFilling(int idx, char c) {\n    int cIdx = c - \'a\';\n    int parentIdx = getParent(idx);\n    if (!eligible[parentIdx][cIdx]) return false;\n    for (auto it = different[parentIdx].begin();\n         it != different[parentIdx].end();\n         ++it) {\n      eligible[getParent(*it)][cIdx] = false;\n    }\n    parentToChar[parentIdx] = c;\n    return true;\n  }\n  \n  string findTheString(vector<vector<int>>& lcp) {\n    int n = lcp.size();\n    idxToParent = vector<int>(n, -1);\n    parentToChar = vector<char>(n, 0);\n    eligible = vector<vector<bool>>(n, vector<bool>(26, true));\n    different = vector<unordered_set<int>>(n);\n    \n    for (int i = 0; i < n; ++i) {\n      if (lcp[i][i] != (n - i)) return "";\n      for (int j = i; j < n; ++j) {\n        if (i < n - 1 && j < n - 1) {\n          if (lcp[i][j] != 0 && ((lcp[i][j] - lcp[i + 1][j + 1]) != 1)) {\n            return "";\n          }\n        }\n        if (lcp[i][j] != lcp[j][i]) return "";\n        if (lcp[i][j] > (n - j)) return "";\n        if (lcp[i][j] != 0) {\n          if (!combineParents(i, j)) return "";\n        } else {\n          if (i == j) return "";\n          different[getParent(i)].insert(getParent(j));\n          different[getParent(j)].insert(getParent(i));\n        }\n      }\n    }\n    \n    for (int i = 0; i < n; ++i) {\n      int parentIdx = getParent(i);\n      if (parentToChar[parentIdx] != 0) continue;\n      bool found = false;\n      for (int j = 0; j < 26; ++j) {\n        if (tryFilling(i, \'a\' + j)) {\n          found = true;\n          break;\n        }\n      }\n      if (!found) {\n        return "";\n      }\n    }\n    string s = "";\n    for (int i = 0; i < n; ++i) {\n      s += parentToChar[getParent(i)];\n    }\n    return s;\n  }\n};\n```
[]