C++ || Union Find || Rolling Hash || String :')
\n# Approach\n1. if lcp[i][j] >= 1 indicates that thier first character equals atleast so, by union find method I will join them and I will do it for all i, j\n
\n# Approach\n1. if lcp[i][j] >= 1 indicates that thier first character equals atleast so, by union find method I will join them and I will do it for all i, j\n2. Now I make the string by traversing from 0 to n - 1. how?\n\n3. Let say I gone to ith index and see its **grand ancestor** by simple find function that we made for the union find now I will see that will it used earlier or not if yes then assign our string that character else assign it new character i.e. we initially initialise with \'a\' and after that do increment. If character exceeds 26 then return null string.\n\n4. Now I have string need to know for every pair what is the longest common prefix and we check with the given. If any pair is wrong then return null string else return our generated string. \n\n---\n\n\n# Complexity\n- Time complexity:\nO(n * n * logn)\n\n---\n\n\n# Code\n```\nclass hashing {\nprivate:\n  int n;\n  long long p;\n  long long mod;\n  vector<long long> P;\n  vector<long long> H;\npublic:\n  hashing(int prime, int md, int N) {\n    n = N;\n    mod = md;\n    p = prime;\n    P.resize(n + 1);\n    H.resize(n + 1);\n  }\n  void init(string& s) {\n    P[0] = 1;\n    for(int i = 1; i <= n; i++) {\n      P[i] = (P[i - 1] % mod * p % mod) % mod;\n      H[i] = (H[i - 1] % mod + ((s[i - 1] - \'a\' + 1) * P[i]) % mod) % mod;\n    }\n  }\n  long long value(int i, int length) {\n    int L = i;\n    int R = i + length - 1;\n    long long res = (H[R] - H[L - 1] + mod) % mod;\n    return res;\n  }\n  bool possible(int i, int j, int length) {\n    long long left = (value(i, length) % mod * P[j - i] % mod) % mod;\n    long long right = value(j, length) % mod;\n    return (left == right);\n  }\n};\nclass Solution {\npublic:\n  int parent[1000];\n  int find(int a) {\n    if(a == parent[a]) {\n      return a;\n    }\n    return parent[a] = find(parent[a]);\n  }\n  void unite(int a, int b) {\n    a = find(a);\n    b = find(b);\n    parent[a] = b;\n  }\n\n  string findTheString(vector<vector<int>>& lcp) {\n    int n = lcp.size();\n    for(int i = 0; i < n; i++) {\n      for(int j = 0; j < n; j++) {\n        if(lcp[i][j] != lcp[j][i]) {\n          return "";\n        }\n        if(min(n - i, n - j) < lcp[i][j]) {\n          return "";\n        }\n      }\n    }\n    for(int i = 0; i < n; i++) {\n      parent[i] = i;\n    }\n    for(int i = 0; i < n; i++) {\n      for(int j = 0; j < n; j++) {\n        if(lcp[i][j]) {\n          unite(i, j);\n        }\n      }\n    }\n    int ch = 0;\n    string s;\n    unordered_map<int, int> assign;\n    for(int i = 0; i < n; i++) {\n      int gp = find(i);\n      if(assign.find(gp) == assign.end()) {\n        if(ch < 26) {\n          assign[gp] = ch;\n          ch++;\n        }\n        else {\n          return "";\n        }\n      }\n      s.push_back(assign[gp] + \'a\');\n    }\n    hashing h1(31, 1e9 + 7, n);\n    hashing h2(37, 1e9 + 9, n);\n    h1.init(s);\n    h2.init(s);\n    for(int i = 0; i < n; i++) {\n      for(int j = i; j < n; j++) {\n        int length = 0;\n        int l = 1, h = n - j;\n        while(l <= h) {\n          int mid = (l + h) >> 1;\n          if(h1.possible(i + 1, j + 1, mid) && h2.possible(i + 1, j + 1, mid)) {\n            length = mid;\n            l = mid + 1;\n          }\n          else {\n            h = mid - 1;\n          }\n        }\n        if(length != lcp[i][j]) {\n          return "";\n        }\n      }\n    }\n    return s;\n  }\n};\n```
['String', 'Union Find', 'Rolling Hash', 'C++']