LeetCode 3474 - Lexicographically Smallest Generated String

We are given two strings: - str1 of length n, containing only 'T' and 'F' - str2 of length m, containing lowercase English letters We must construct a string word of length n + m - 1.

leetcodehardstringgreedystring-matching

LeetCode Problem 3474

Difficulty: 🔴 Hard
Topics: String, Greedy, String Matching

Solution

LeetCode 3474 - Lexicographically Smallest Generated String

Problem Understanding

We are given two strings:

  • str1 of length n, containing only 'T' and 'F'
  • str2 of length m, containing lowercase English letters

We must construct a string word of length n + m - 1.

For every position i in str1, the substring of word starting at i and having length m must satisfy one of two conditions:

  • If str1[i] == 'T', then word[i:i+m] must be exactly equal to str2.
  • If str1[i] == 'F', then word[i:i+m] must not be equal to str2.

Among all valid generated strings, we must return the lexicographically smallest one. If no valid string exists, we return the empty string.

The most important observation is that every 'T' position creates hard equality constraints on a length-m segment of the final string. Multiple 'T' segments may overlap, and those overlaps must be consistent. If two overlapping 'T' constraints force different characters into the same position, the answer is immediately impossible.

The constraints are relatively large. n can be up to 10^4 and m can be up to 500, so solutions that enumerate all possible strings are completely infeasible. We need a constructive greedy approach.

Several edge cases deserve attention immediately. Multiple 'T' windows may overlap and conflict. An 'F' window may become unavoidably equal to str2 because every position in that window is forced by 'T' constraints. Some windows may overlap heavily, so modifying a character to satisfy one 'F' constraint can affect many others.

Approaches

Brute Force

A brute force approach would try to generate all possible strings of length n + m - 1 and test whether each one satisfies all constraints.

This is clearly impossible. Even if the alphabet were restricted to lowercase letters, the search space would be:

$$26^{(n+m-1)}$$

which grows exponentially.

The brute force method is conceptually correct because it checks every possible candidate and returns the smallest valid one, but it is far beyond the limits imposed by the problem.

Key Insight

The 'T' constraints are mandatory and completely determine portions of the answer.

If a window starting at index i must equal str2, then every position i + j is forced to contain str2[j].

Therefore, we first place all characters required by 'T' constraints and verify that no conflicts occur.

After that, every still-unassigned position should be filled with 'a', because we want the lexicographically smallest possible string.

At this point, some 'F' windows may accidentally equal str2. Whenever that happens, we must deliberately break the equality.

To keep the string lexicographically smallest, we modify the rightmost available non-forced position inside that window. Changing a later position has less impact on lexicographic order than changing an earlier one.

The replacement character should be the smallest character different from the corresponding character of str2. If the required character is 'a', we use 'b'; otherwise we use 'a'.

After all repairs are performed, we perform a final verification pass.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries all possible strings
Optimal Greedy Construction O(nm) O(n + m) Construct answer directly from constraints

Algorithm Walkthrough

  1. Let L = n + m - 1, the required length of the generated string.
  2. Create an array word of length L, initially unassigned. Also maintain a boolean array fixed indicating whether a position is forced by a 'T' constraint.
  3. For every index i where str1[i] == 'T', place the entire pattern str2 into positions i through i + m - 1.
  • If a position is unassigned, store the required character.
  • If a position already contains a different character, the constraints conflict and the answer is impossible.
  1. After processing all 'T' constraints, fill every still-unassigned position with 'a'.

This gives the lexicographically smallest string among all strings satisfying the mandatory equality constraints. 5. Process every index i where str1[i] == 'F'.

  • Check whether word[i:i+m] currently equals str2.
  • If it does not equal str2, this constraint is already satisfied.
  • If it does equal str2, we must break the equality.
  1. To break equality, scan the window from right to left and find the rightmost position that is not fixed by a 'T' constraint.

  • If no such position exists, then the window is permanently forced to equal str2, so return "".

  • Otherwise modify that position:

  • If the matching character of str2 is 'a', write 'b'.

  • Otherwise write 'a'.

  1. After all 'F' windows have been processed, perform a complete validation pass.
  • Every 'T' window must equal str2.
  • Every 'F' window must differ from str2.
  1. If validation succeeds, return the constructed string.

Why it works

The mandatory 'T' constraints are handled first because any valid solution must satisfy them. Filling all remaining positions with 'a' produces the smallest possible starting point. Whenever an 'F' window still equals str2, we must change something inside that window. Modifying the rightmost available non-forced position preserves lexicographic minimality because later characters affect lexicographic order less than earlier characters. The final validation guarantees that all constraints are satisfied.

Python Solution

class Solution:
    def generateString(self, str1: str, str2: str) -> str:
        n = len(str1)
        m = len(str2)
        length = n + m - 1

        word = ['?'] * length
        fixed = [False] * length

        # Apply all T constraints
        for i in range(n):
            if str1[i] != 'T':
                continue

            for j in range(m):
                pos = i + j
                ch = str2[j]

                if word[pos] != '?' and word[pos] != ch:
                    return ""

                word[pos] = ch
                fixed[pos] = True

        # Fill remaining positions with 'a'
        for i in range(length):
            if word[i] == '?':
                word[i] = 'a'

        # Fix violating F windows
        for i in range(n):
            if str1[i] != 'F':
                continue

            equal = True
            for j in range(m):
                if word[i + j] != str2[j]:
                    equal = False
                    break

            if not equal:
                continue

            change_pos = -1

            for j in range(m - 1, -1, -1):
                pos = i + j
                if not fixed[pos]:
                    change_pos = pos
                    offset = j
                    break

            if change_pos == -1:
                return ""

            if str2[offset] == 'a':
                word[change_pos] = 'b'
            else:
                word[change_pos] = 'a'

        result = ''.join(word)

        # Final verification
        for i in range(n):
            substring = result[i:i + m]

            if str1[i] == 'T':
                if substring != str2:
                    return ""
            else:
                if substring == str2:
                    return ""

        return result

The implementation follows the construction process directly. The first phase applies every mandatory equality constraint. The second phase fills all remaining positions with 'a', which gives the smallest possible starting string. The third phase repairs any 'F' window that still equals str2 by modifying the rightmost mutable character. Finally, a complete validation pass ensures correctness.

Go Solution

func generateString(str1 string, str2 string) string {
	n := len(str1)
	m := len(str2)
	length := n + m - 1

	word := make([]byte, length)
	fixed := make([]bool, length)

	for i := 0; i < length; i++ {
		word[i] = '?'
	}

	// Apply T constraints
	for i := 0; i < n; i++ {
		if str1[i] != 'T' {
			continue
		}

		for j := 0; j < m; j++ {
			pos := i + j

			if word[pos] != '?' && word[pos] != str2[j] {
				return ""
			}

			word[pos] = str2[j]
			fixed[pos] = true
		}
	}

	// Fill remaining positions with 'a'
	for i := 0; i < length; i++ {
		if word[i] == '?' {
			word[i] = 'a'
		}
	}

	// Fix F windows
	for i := 0; i < n; i++ {
		if str1[i] != 'F' {
			continue
		}

		equal := true
		for j := 0; j < m; j++ {
			if word[i+j] != str2[j] {
				equal = false
				break
			}
		}

		if !equal {
			continue
		}

		changePos := -1
		offset := -1

		for j := m - 1; j >= 0; j-- {
			pos := i + j
			if !fixed[pos] {
				changePos = pos
				offset = j
				break
			}
		}

		if changePos == -1 {
			return ""
		}

		if str2[offset] == 'a' {
			word[changePos] = 'b'
		} else {
			word[changePos] = 'a'
		}
	}

	result := string(word)

	// Final verification
	for i := 0; i < n; i++ {
		sub := result[i : i+m]

		if str1[i] == 'T' {
			if sub != str2 {
				return ""
			}
		} else {
			if sub == str2 {
				return ""
			}
		}
	}

	return result
}

The Go implementation mirrors the Python version. The primary difference is the use of []byte for efficient character updates. Since string characters are immutable in Go, constructing the answer through a byte slice avoids repeated string allocations. No special overflow handling is required because all indices remain well within Go's integer range.

Worked Examples

Example 1

Input

str1 = "TFTF"
str2 = "ab"

Here:

  • n = 4
  • m = 2
  • L = 5

After applying all 'T' constraints:

Position 0 1 2 3 4
Value a b a b ?

Fill remaining positions with 'a':

Position 0 1 2 3 4
Value a b a b a

String becomes "ababa".

Check F windows:

Index Window Equals "ab"?
1 "ba" No
3 "ba" No

Result:

"ababa"

Example 2

Input

str1 = "TFTF"
str2 = "abc"

Apply 'T' at positions 0 and 2.

Window at 0 forces:

abc??

Window at 2 forces:

ababc

Position 2 must simultaneously be:

c

from the first window and

a

from the second window.

This conflict makes the construction impossible.

Result:

""

Example 3

Input

str1 = "F"
str2 = "d"

Length:

L = 1

No 'T' constraints exist.

Initial string:

"a"

Check the only F window:

"a" != "d"

Constraint satisfied.

Result:

"a"

Complexity Analysis

Measure Complexity Explanation
Time O(nm) Each constraint window may be scanned a constant number of times
Space O(n + m) Storage for the constructed string and fixed-position markers

The dominant work comes from examining windows of length m across all n positions. Since m ≤ 500 and n ≤ 10^4, the total work is roughly five million character comparisons, which is easily acceptable.

Test Cases

s = Solution()

assert s.generateString("TFTF", "ab") == "ababa"      # example 1
assert s.generateString("TFTF", "abc") == ""          # example 2
assert s.generateString("F", "d") == "a"             # example 3

assert s.generateString("T", "a") == "a"            # single forced character
assert s.generateString("F", "a") == "b"            # must differ from 'a'

assert s.generateString("TT", "aa") == "aaa"        # overlapping compatible T windows
assert s.generateString("TT", "ab") == ""           # overlapping conflicting T windows

assert s.generateString("FF", "aa") == "aba"        # overlapping F constraints

assert s.generateString("TF", "ab") == "aba"        # T followed by F

assert s.generateString("FT", "ab") == "aab"        # F before T

assert s.generateString("FFF", "a") == "bbb"        # every window must differ from 'a'

assert s.generateString("T", "z") == "z"            # non-'a' forced character

Test Summary

Test Why
("TFTF", "ab") Official example, valid construction
("TFTF", "abc") Official example, conflicting constraints
("F", "d") Official example, smallest free character
("T", "a") Single mandatory match
("F", "a") Single mandatory mismatch
("TT", "aa") Compatible overlapping T windows
("TT", "ab") Incompatible overlapping T windows
("FF", "aa") Overlapping F windows
("TF", "ab") Mixed constraints
("FT", "ab") Reverse mixed constraints
("FFF", "a") Every position requires modification
("T", "z") Forced non-default character

Edge Cases

One important edge case occurs when two 'T' windows overlap and require different characters at the same position. In that situation no valid generated string exists. The implementation detects this immediately while applying the mandatory constraints and returns the empty string.

Another critical case occurs when an 'F' window is completely determined by overlapping 'T' constraints. If that window equals str2 and every position inside it is fixed, there is no available character that can be changed to break the equality. The algorithm explicitly searches for a non-fixed position and returns "" when none exists.

A third subtle case involves lexicographic minimization. A naive solution might modify the first available position inside an offending 'F' window. Doing so can produce a valid answer but not the smallest one. By changing the rightmost mutable position instead, the algorithm preserves smaller characters earlier in the string, guaranteeing the lexicographically smallest valid construction.