Leet Code Weekly Contest 261

1. Minimum Moves to Convert String

Simple DP.

F_i = \begin{cases} F_{i + 1} & S_i = 'O' \\ F_{i + 3} + 1 & S_i = '1' \land i + 3 <= n \\ 1 & S_i = '1' \land i + 3 > n \\ \end{cases}

c++

class Solution {
public:
  int minimumMoves(string s)
  {
    int n = s.length();
    int *f = new int[n + 1];

    f[n] = 0;
    for (int i = n - 1; i >= 0; i--)
    {
      if (s[i] == 'O')
      {
        f[i] = f[i + 1];
      }
      else
      {
        f[i] = ((i + 3 <= n) ? f[i + 3] : 0) + 1;
      }
    }

    return f[0];
  }
};

2. Find Missing Observations

Assume there are $n$ elements left there and the target sum is $s$ , always keep $n \leq s \leq 6 \times n$ .

c++

class Solution {
public:
  vector<int> missingRolls(vector<int>& rolls, int mean, int n)
  {
    int m = rolls.size();

    int sum = 0;
    for (int i = 0; i < m; i++)
    {
      sum += rolls[i];
    }

    int diff = mean * (n + m) - sum;

    auto result = vector<int>();

    if (diff >= n && diff <= 6 * n)
      for (int i = 1; i <= n; i++)
      {
        for (int j = 1; j <= 6; j++)
        {
          int rest = diff - j;

          if (rest >= (n - i) && rest <= 6 * (n - i))
          {
            result.push_back(j);
            diff = rest;
            break;
          }
        }
      }

    return result;
  }
};

3. Stone Game IX

Game theory. First, count the stones by their values mod $3$ . Assume the current $sum \mod 3$ is $x$ , then we can have the following state transitions (under optimal situation).

c++

class Solution {
public:

    bool f(int x, int n0, int n1, int n2)
    {
      if (n1 == n2)
      {
        return true;
      }

      if (x == 1 && (n1 == n2 + 1 || n1 == n2))
      {
        return true;
      }

      if (x == 2 && (n2 == n1 + 1 || n2 == n1))
      {
        return true;
      }

      int steps = n0;

      if (x == 1 && n1 > n2)
      {
        steps++;
      }

      if (x == 2 && n2 > n1)
      {
        steps++;
      }

      return steps % 2 == 1;
    }

    bool stoneGameIX(vector<int>& stones)
    {
      int n[3] = { 0, 0, 0 };
      for (int i = 0; i < stones.size(); i++)
      {
        n[stones[i] % 3]++;
      }

      if (n[1] > 0 && f(1, n[0], n[1] - 1, n[2]) == false)
      {
        return true;
      }

      if (n[2] > 0 && f(2, n[0], n[1], n[2] - 1) == false)
      {
        return true;
      }

      return false;
    }
};

4. Smallest K-Length Subsequence With Occurrences of a Letter

First, we can easily pre-calcuate two functions in $O(n)$ time.

$F_i$ the number of occurrences (for the letter) from $i$ to the end of the string.
$G_{i, c}$ the first occurence position of letter $c$ from $i$ to the end of the string.

Then, given a state $(i, head, cnt)$ where

$i$ the $i-th$ letter in result you're trying to determine.
$head$ the start position of the rest of the string.
$cnt$ is the number of occurences you earned already.

You can now iterate the best next letter $c$ (from low to high) and make sure it meets the conditions:

After $c$ , you can still achive the number of repetitions $r$ .
After $c$ , you can still concat enough letters (to the length $k$ ).

The time complexity is $O(n)$ .

c++

class Solution {
public:
  
  int f[50001], g[50001][26];

  void init(string s, char letter)
  {
    int n = s.length();

    f[n] = 0;
    for (int i = n - 1; i >= 0; i--)
    {
      f[i] = f[i + 1] + (s[i] == letter);
    }

    for (int c = 0; c < 26; c++)
    {
      g[n][c] = INT_MAX;
    }

    for (int i = n - 1; i >= 0; i--)
    {
      memcpy(&g[i][0], &g[i + 1][0], sizeof(int) * 26);
      g[i][s[i] - 'a'] = i;
    }
  }

  string solve(string s, int k, char letter, int r)
  {
    int n = s.length();

    string ans = "";
    for (int i = 0, head = 0, cnt = 0; i < k; i++)
    {
      // cout << "i = " << i << ", head = " << head << ", cnt = " << cnt << endl;

      bool found = false;
      for (int c = 0; c < 26; c++)
      {
        int first = g[head][c];
        
        if (first == INT_MAX) continue;
        
        int delta = c == (letter - 'a');

        if (r <= (cnt + delta + min(k - 1 - i, f[first + 1])) && (n - first - 1) >= (k - i - 1))
        {
          // cout << "take (" << i << ") = " << s[i] << endl;
          ans += (char) ('a' + c);
          head = first + 1;
          cnt += delta;
          found = true;
          break;
        }
      }

      if (!found)
      {
        return "FAILED";
      }
    }
    
    return ans;
  }

  string smallestSubsequence(string s, int k, char letter, int repetition)
  {
    init(s, letter);
    return solve(s, k, letter, repetition);
  }
};

Leet Code Weekly Contest 261

1. Minimum Moves to Convert String

2. Find Missing Observations

3. Stone Game IX

4. Smallest K-Length Subsequence With Occurrences of a Letter

COMMAND INTERFACE

:help aguang.xyz