3399. Smallest Substring With Identical Characters II LeetCode Solution

In this guide, you will get 3399. Smallest Substring With Identical Characters II LeetCode Solution with the best time and space complexity. The solution to Smallest Substring With Identical Characters II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Smallest Substring With Identical Characters II solution in C++
Smallest Substring With Identical Characters II solution in Java
Smallest Substring With Identical Characters II solution in Python
Additional Resources

3399. Smallest Substring With Identical Characters II LeetCode Solution image

Problem Statement of Smallest Substring With Identical Characters II

You are given a binary string s of length n and an integer numOps.
You are allowed to perform the following operation on s at most numOps times:

Select any index i (where 0 <= i < n) and flip s[i]. If s[i] == '1', change s[i] to '0' and vice versa.

You need to minimize the length of the longest substring of s such that all the characters in the substring are identical.
Return the minimum length after the operations.

Example 1:

Input: s = “000001”, numOps = 1
Output: 2
Explanation:
By changing s[2] to ‘1’, s becomes “001001”. The longest substrings with identical characters are s[0..1] and s[3..4].

Example 2:

Input: s = “0000”, numOps = 2
Output: 1
Explanation:
By changing s[0] and s[2] to ‘1’, s becomes “1010”.

Example 3:

Input: s = “0101”, numOps = 0
Output: 1

Constraints:

1 <= n == s.length <= 105
s consists only of '0' and '1'.
0 <= numOps <= n

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(1)

3399. Smallest Substring With Identical Characters II LeetCode Solution in C++

class Solution {
 public:
  // Same as 3398. Smallest Substring With Identical Characters I
  int minLength(string s, int numOps) {
    int l = 1;
    int r = s.length();

    while (l < r) {
      const int m = (l + r) / 2;
      if (getMinOps(s, m) <= numOps)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

 private:
  // Returns the minimum number of operations needed to make all groups of
  // identical characters of length k or less.
  int getMinOps(const string& s, int k) {
    if (k == 1) {
      size_t res = 0;
      for (int i = 0; i < s.length(); ++i)
        if (s[i] - '0' == i % 2)
          ++res;
      return min(res, s.length() - res);
    }

    int res = 0;
    int runningLen = 1;

    for (int i = 1; i < s.length(); ++i)
      if (s[i] == s[i - 1]) {
        ++runningLen;
      } else {
        res += runningLen / (k + 1);
        runningLen = 1;
      }

    return res + runningLen / (k + 1);
  }
};
/* code provided by PROGIEZ */

3399. Smallest Substring With Identical Characters II LeetCode Solution in Java

class Solution {
  // Same as 3398. Smallest Substring With Identical Characters I
  public int minLength(String s, int numOps) {
    int l = 1;
    int r = s.length();

    while (l < r) {
      final int m = (l + r) / 2;
      if (getMinOps(s, m) <= numOps)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

  // Returns the minimum number of operations needed to make all groups of
  // identical characters of length k or less.
  private int getMinOps(final String s, int k) {
    if (k == 1) {
      int res = 0;
      for (int i = 0; i < s.length(); ++i)
        if (s.charAt(i) - '0' == i % 2)
          ++res;
      return Math.min(res, s.length() - res);
    }

    int res = 0;
    int runningLen = 1;

    for (int i = 1; i < s.length(); ++i)
      if (s.charAt(i) == s.charAt(i - 1)) {
        ++runningLen;
      } else {
        res += runningLen / (k + 1);
        runningLen = 1;
      }

    return res + runningLen / (k + 1);
  }
}
// code provided by PROGIEZ

3399. Smallest Substring With Identical Characters II LeetCode Solution in Python

class Solution:
  # Same as 3398. Smallest Substring With Identical Characters I
  def minLength(self, s: str, numOps: int) -> int:
    def getMinOps(k: int) -> int:
      """
      Returns the minimum number of operations needed to make all groups of
      identical characters of length k or less.
      """
      if k == 1:
        res = sum(1 for i, c in enumerate(s) if int(c) == i % 2)
        return min(res, len(s) - res)

      res = 0
      runningLen = 1

      for a, b in itertools.pairwise(s):
        if a == b:
          runningLen += 1
        else:
          res += runningLen // (k + 1)
          runningLen = 1

      return res + runningLen // (k + 1)

    return bisect_left(range(1, len(s) + 1),
                       True, key=lambda m: getMinOps(m) <= numOps)
 # code by PROGIEZ