main.cpp

// Source: https://leetcode.com/problems/lexicographically-smallest-generated-string
// Title: Lexicographically Smallest Generated String
// Difficulty: Hard
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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 <= 10^4`
// - `1 <= m == str2.length <= 500`
// - `str1` consists only of `'T'` or `'F'`.
// - `str2` consists only of lowercase English characters.
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <bitset>
#include <vector>

using namespace std;

// Greedy + Bit Mask
//
// We initialize the output string `s` with all letter `a`.
// Fill the `s` by str1[i]=T and mark these position as fixed.
//
// Now we need to fill the free slots.
// Focus on each s[i:i+m) with str1[i] = F.
// If s[i:i+m) != str2, then it is already done.
// Otherwise, since we want s to be lexicographically smallest,
// we will always change the last free slot in s[i:i+m).
// However, we don't want to break previous "done" F.
//
// To avoid that, precompute the last free slot of each F.
// Now we loop through the free slots.
// Pick all F that corresponds to this slot as the last,
// check this slot is important for the constraint (i.e. other position are matched).
// If so, we use a bitmask to track which letter is not allowed for this slot.
// After checking all F for this slot, we pick the smallest allowed letter.
class Solution {
  struct Mask : bitset<26> {
    int low_zero() const {  // find lowest zero
      return countr_one(to_ulong());
    }
  };

  using Bool = unsigned char;

 public:
  string generateString(const string& str1, const string& str2) {
    const int n = str1.size(), m = str2.size();
    const int l = n + m - 1;
    auto s = string(l, 'a');  // fill with all a
    auto fixed = vector<Bool>(l, false);
    auto slotToIdxs = vector<vector<int>>(l);  // free slot -> F index

    // Fill by T
    for (int i = 0; i < n; ++i) {
      if (str1[i] != 'T') continue;

      for (int j = i; j < i + m; ++j) {
        if (fixed[j] && s[j] != str2[j - i]) return "";  // invalid
        s[j] = str2[j - i];
        fixed[j] = true;
      }
    }

    // Find free slot
    for (int i = 0; i < n; ++i) {
      if (str1[i] != 'F') continue;

      // Check done
      bool done = false;
      for (int j = i; j < i + m; ++j) {
        if (s[j] != str2[j - i]) {
          done = true;
          break;
        }
      }
      if (done) continue;

      // Find last free slot
      int lastSlot = -1;
      for (int j = i + m - 1; j >= i; --j) {
        if (!fixed[j]) {
          lastSlot = j;
          break;
        }
      }
      if (lastSlot == -1) return "";  // invalid
      slotToIdxs[lastSlot].push_back(i);
    }

    // Loop for slots
    for (int slot = 0; slot < l; ++slot) {
      if (fixed[slot]) continue;

      Mask disallowed;  // disallowed letters
      for (int i : slotToIdxs[slot]) {
        // Check done
        bool done = false;
        for (int j = i; j < i + m; ++j) {
          if (j == slot) continue;
          if (s[j] != str2[j - i]) {
            done = true;
            break;
          }
        }
        if (done) continue;

        // Exclude letter
        disallowed.set(str2[slot - i] - 'a');
      }

      if (disallowed.all()) return "";  // no allowed letter
      s[slot] = disallowed.low_zero() + 'a';
    }

    return s;
  }
};

// Greedy + Insight
//
// We "notice" that the free slot is either `a` or `b`.
// (why????????????????)
//
// We initialize the output string `s` with all letter `a`.
// Next fill the `s` by str1[i]=T.
// Next loop for each str1[i]=F.
// If s[i:i+m) != str2, then it is already done.
// Otherwise, find the last free slot and change it to `b`.
class Solution2 {
  using Bool = unsigned char;

 public:
  string generateString(const string& str1, const string& str2) {
    const int n = str1.size(), m = str2.size();
    const int l = n + m - 1;
    auto s = string(l, 'a');  // fill with all a
    auto fixed = vector<Bool>(l, false);

    // Fill by T
    for (int i = 0; i < n; ++i) {
      if (str1[i] != 'T') continue;

      for (int j = i; j < i + m; ++j) {
        if (fixed[j] && s[j] != str2[j - i]) return "";  // invalid
        s[j] = str2[j - i];
        fixed[j] = true;
      }
    }

    // Greedy
    for (int i = 0; i < n; ++i) {
      if (str1[i] != 'F') continue;

      // check if is already done
      bool flag = false;
      for (int j = i; j < i + m; ++j) {
        if (s[j] != str2[j - i]) {
          flag = true;
          break;
        }
      }
      if (flag) continue;

      // Find last free slot
      int idx = -1;
      for (int j = i + m - 1; j >= i; --j) {
        if (!fixed[j]) {
          idx = j;
          break;
        }
      }
      if (idx == -1) return "";

      s[idx] = 'b';  // change to b
      // fixed[idx] = true; // don't need this (why????????????????)
    }

    return s;
  }
};