0
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ (Down-voters please comment.) \$\endgroup\$ – greybeard Jun 16 at 3:51
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Code Gorilla Jun 18 at 7:31
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Damien Jun 18 at 14:24
1
\$\begingroup\$

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";
    
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.