2573. Find the String with LCP
Intuition\nTo build a string, we will sequentially analyze arrays, while separately storing the next character and the next character in alphabetical order\n\n#
# Intuition\nTo build a string, we will sequentially analyze arrays, while separately storing the next character and the next character in alphabetical order\n\n# Approach\nTo check the correctness of arrays, we use the z-function\n\n# Complexity\n- Time complexity:\n$$O(log(n))$$\n\n- Space complexity:\n$$O(log(n))$$\n\n# Code\n```\nclass Solution {\n    fun findTheString(lcp: Array<IntArray>): String {\n        if (lcp.size == 1 && lcp[0][0] == 0) return ""\n\n        val result = CharArray(lcp[0].size) { _: Int ->  \'#\' }\n        result[0] = \'a\'\n        var next = \'a\'\n        var dNext = \'a\'\n        for (ind in lcp.indices) {\n            if (lcp[ind].last() > 1) return ""\n\n            val arrForBuild = lcp[ind].takeLast(lcp.size - ind).toIntArray()\n            arrForBuild.forEachIndexed { index, arr ->\n                if (index > 0 && result[index + ind] == \'#\' && arr > 0) result[index + ind] = next\n            }\n            if (result[ind] == \'#\') result[ind] = next\n            next = if (1 < arrForBuild.size) {\n                if (arrForBuild.all { it == 0 }) {\n                    next\n                } else {\n                    if (result[ind + 1] != \'#\') result[ind + 1] else {\n                        if (dNext == \'z\') \'a\' else {\n                            dNext += 1\n                            dNext\n                        }\n                    }\n                }\n            } else {\n                next\n            }\n        }\n        var s = String(result)\n\n        val length = s.length\n        if (s.isEmpty()) return ""\n        for (ind in lcp.indices) {\n            val prefStr = if (ind == 0) s else s.takeLast(length - ind) + "#" + s\n            val zArr = zFunction(prefStr)\n            val zArrM = zArr.takeLast(length).toIntArray()\n            zArrM[ind] = length - ind\n            if (zArrM.joinToString() != lcp[ind].joinToString()) {\n                s =  ""\n                break\n            }\n        }\n\n        return s\n    }\n    \n    fun zFunction(s : String): IntArray {\n        val n = s.length\n        val zf = IntArray(n)\n        var left = 0\n        var right = 0\n        for (i in 1 until n) {\n            val min = if(right - i < zf[i - left]) right - i else zf[i - left] \n            zf[i] = if(0 > min) 0 else min\n            while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]]) {\n                zf[i]++\n            }\n            if (i + zf[i] > right) {\n                left = i\n                right = i + zf[i]\n            }\n        }\n        return zf\n    }\n\n}\n```
['String', 'Dynamic Programming', 'Greedy', 'Kotlin']