[JAVA] building string from scratch and validate the LCP array
Intuition\n Describe your first thoughts on how to solve this problem. \nWe are given 2D integer array. lcp[i][j] indicates length of longest common prefix. We 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe are given 2D integer array. lcp[i][j] indicates length of longest common prefix. We need to find the lexicographically smaller string consist of a-z.\n\nWe can write a validation algorithem to check if such a stirng can be build. If not we can return empty string.\n\nAfter building the array, we are not violating the LCP property.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n## Validation\n* lcp[i][j] should be same sa lcp[j][i]\n* when i and j is same, that means when we are looking the same index, loc[i][i] should equal to length of remaining string. loc[i][i] = len-i\n* When we build lexigrohpically small string, we should not cross a-z limit.\n\n# Complexity\nn - length of string\n- Time complexity: $$O(n*n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public String findTheString(int[][] lcp) {\n        var len = lcp.length;\n        var arr = new char[len];\n        var val = \'a\';\n        \n        for(int i = 0; i < len; i++)\n        {\n            if(lcp[i][i] != len-i ) return "";\n            if(arr[i] == 0)\n            {\n                arr[i] = val;\n                val++;\n            }\n            \n            for(int j  = i+1; j < len; j++)\n            {\n                if(lcp[i][j] != lcp[j][i] ||  i + lcp[i][j] >= len  ) return "";\n                if(lcp[i][j] == 0)\n                {\n                    if(arr[i] == 0)\n                    {\n                        arr[j] = val;\n                        val++;\n                    }\n                }else{\n                    for(int k = 0; k < lcp[i][j]; k++ )\n                    {\n                        if(arr[j+k] == 0 )\n                        {\n                           arr[j+k] = arr[i+k];\n                        }else{\n                            if(arr[j+k] - arr[i+k] != 0)  return "";\n                        }\n                    }\n                }\n            }\n        }\n        //reverse validation\n        for(int i = 0; i < len; i++)\n        {\n            if(arr[i] - \'a\' >= 26) return "";\n            for(int j = i+1; j < len; j++)\n            {\n                var k = lcp[i][j];\n                if( j+ k < len &&  arr[i+k] == arr[j + k] ) return "";\n            }\n        }\n        return new String(arr);\n    }\n}\n```
['Java']