LeetCode in Kotlin

3474. Lexicographically Smallest Generated String

Hard

You are given two strings, str1 and str2, of lengths n and m, respectively.

A string word of length n + m - 1 is defined to be generated by str1 and str2 if it satisfies the following conditions for each index 0 <= i <= n - 1:

• If str1[i] == 'T', the substring of word with size m starting at index i is equal to str2, i.e., word[i..(i + m - 1)] == str2.
• If str1[i] == 'F', the substring of word with size m starting at index i is not equal to str2, i.e., word[i..(i + m - 1)] != str2.

Return the lexicographically smallest possible string that can be generated by str1 and str2. If no string can be generated, return an empty string "".

Example 1:

Input: str1 = “TFTF”, str2 = “ab”

Output: “ababa”

Explanation:

The table below represents the string "ababa"

Index	T/F	Substring of length m
0	‘T’	“ab”
1	‘F’	“ba”
2	‘T’	“ab”
3	‘F’	“ba”

The strings "ababa" and "ababb" can be generated by str1 and str2.

Return "ababa" since it is the lexicographically smaller string.

Example 2:

Input: str1 = “TFTF”, str2 = “abc”

Output: “”

Explanation:

No string that satisfies the conditions can be generated.

Example 3:

Input: str1 = “F”, str2 = “d”

Output: “a”

Constraints:

• 1 <= n == str1.length <= 104
• 1 <= m == str2.length <= 500
• str1 consists only of 'T' or 'F'.
• str2 consists only of lowercase English characters.

Solution

class Solution {
    fun generateString(str1: String, str2: String): String {
        val n = str1.length
        val m = str2.length
        val l = n + m - 1
        val word = arrayOfNulls<Char>(l)
        for (i in 0..<n) {
            if (str1[i] == 'T') {
                for (j in 0..<m) {
                    val pos = i + j
                    if (word[pos] != null && word[pos] != str2[j]) {
                        return ""
                    }
                    word[pos] = str2[j]
                }
            }
        }
        val free = BooleanArray(l)
        for (i in 0..<l) {
            if (word[i] == null) {
                word[i] = 'a'
                free[i] = true
            }
        }
        if (n == 0) {
            return "a".repeat(l)
        }
        for (i in 0..<n) {
            if (str1[i] == 'F' && intervalEquals(word, str2, i, m)) {
                var fixed = false
                for (j in m - 1 downTo 0) {
                    val pos = i + j
                    if (free[pos]) {
                        word[pos] = 'b'
                        free[pos] = false
                        fixed = true
                        break
                    }
                }
                if (!fixed) {
                    return ""
                }
            }
        }
        val sb = StringBuilder()
        for (c in word) {
            sb.append(c)
        }
        return sb.toString()
    }

    private fun intervalEquals(word: Array<Char?>, str2: String, i: Int, m: Int): Boolean {
        for (j in 0..<m) {
            if (word[i + j] == null || word[i + j] != str2[j]) {
                return false
            }
        }
        return true
    }
}

This site is open source. Improve this page.