3398. Smallest Substring With Identical Characters I LeetCode Solution

In this guide, you will get 3398. Smallest Substring With Identical Characters I LeetCode Solution with the best time and space complexity. The solution to Smallest Substring With Identical Characters I 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 I solution in C++
Smallest Substring With Identical Characters I solution in Java
Smallest Substring With Identical Characters I solution in Python
Additional Resources

3398. Smallest Substring With Identical Characters I LeetCode Solution image

Problem Statement of Smallest Substring With Identical Characters I

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 <= 1000
s consists only of '0' and '1'.
0 <= numOps <= n

Complexity Analysis

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

3398. Smallest Substring With Identical Characters I LeetCode Solution in C++

class Solution {
 public:
  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 */

3398. Smallest Substring With Identical Characters I LeetCode Solution in Java

class Solution {
  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

3398. Smallest Substring With Identical Characters I LeetCode Solution in Python

class Solution:
  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