LeetCode 76: Minimum Window Substring

Question

I'm posting an sliding window problem of LeetCode (Minimum Window Substring) with C++. If you have time and would like to review the code, please do so, I appreciate that.

On LeetCode, we are only allowed to change the variable names and brute force algorithms are discouraged, usually fail with TLE (Time Limit Error) or MLE (Memory Limit Error).

Problem

Given a string base_string and a string target, find the minimum window in base_string which will contain all the characters in target in complexity O(n).

Example:

Input: base_string = "ADOBECODEBANC", target = "ABC" Output: "BANC" Note:

If there is no such window in base_string that covers all characters in target, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in base_string.

C++

class Solution {
public:
 string minWindow(string base_string, string target) {
 vector<int> count_map(128, 0);
 for (auto character : target)
 count_map[character]++;
 int left = 0, right = 0;
 int min_left = 0, min_right = INT_MAX;
 int target_length = target.size();
 while (right < base_string.size()) {
 if (count_map[base_string[right++]]-- > 0)
 target_length--;
 while (target_length == 0) {
 if (right - left < min_right)
 min_right = right - (min_left = left);
 if (count_map[base_string[left++]]++ == 0)
 target_length++;
 }
 }
 return min_right == INT_MAX ? "" : base_string.substr(min_left, min_right);
 }
};

Reference

• Question

• Solution

• Discussion

• greybeard: (Down-voters please comment.)
• Code Gorilla: I can’t see anything wrong with the question, maybe the links but it took me three reads to think I understood it. You might want to consider ++var for non-pod types.
• Damien: What happens when you submit this code to LeetCode? Did you pass the TL? Why do you think it can be further improved? Comparison with competitor results? (I didn't donwvote)

Answer 1

In the following code, I tried two modifications.

1. I slightly modified the way tests are performed, in order to minimize them a little bit

2. I used iterators, like this :auto p_str = base_string.begin() + right;

with the idea to avoid a redirection here:

count_map[*p_str++]--;

instead of

count_map[base_string[right++]]--;

At the end, we cannot be sure how much the speed has been improved. A benchmark is needed (by LeetCode?). We can only be sure that the code is more difficult to read!

#include <iostream>
#include <string>
#include <vector>
#include <cassert>
std::string minWindow(std::string base_string, std::string target) {
 std::vector<int> count_map(128, 0);
 int n = base_string.length();
 for (auto character : target)
 count_map[character]++;
 int left = 0, right = 0;
 int min_left = 0, min_right = n+1;
 int target_length = target.size();
 while (right < n) {
 auto p_str = base_string.begin() + right;
 while (target_length > 0 && p_str != base_string.end()) {
 if (count_map[*p_str++]-- > 0)
 target_length--;
 }
 right = p_str - base_string.begin();
 
 if (target_length == 0 && right - left < min_right)
 min_right = right - left;
 p_str = base_string.begin() + left;
 while (target_length == 0) {
 if (count_map[*p_str++]++ == 0) {
 left = p_str - base_string.begin() - 1;
 if (right - left < min_right)
 min_right = right - (min_left = left);
 target_length++;
 }
 }
 left = p_str - base_string.begin();
 }
 if (target_length == 0 && (right - left < min_right))
 min_right = right - (min_left = left);
 
 return min_right == n ? "" : base_string.substr(min_left, min_right);
}
int main() {
 std::string s = "XXXABYYCTTTABYC";
 std::string target = "CBA";
 std::cout << minWindow (s, target) << "\n";
 
}