loading...

Daily Coding Challenge #11

wingkwong profile image Wing-Kam ・2 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
Educational Codeforces Round 87 (Rated for Div. 2) - B - Ternary String
https://codeforces.com/contest/1354/problem/B
*/

#include <bits/stdc++.h>
using namespace std; 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)

string helper(string s, string t) {
    vector<int> hist(128, 0);
    for (char c:t) hist[c]++;
    int cnt=t.size(),begin=0,end=0,minStart=0,minLen=INT_MAX;
    // move end pointer to locate a valid window
    while (end<s.size()){
        // if the char s[end] exists in the map, decrease the counter   
        // decrease hist[s[end]], if char doesn't exist, hist[s[end]] will be negative
        if (--hist[s[end++]]>=0) cnt--;
        // cnt==0 means the window is valid
        while (cnt==0){
            // move start pointer to locate a smaller window
            if (end-begin<minLen){
                minLen=end-begin;
                minStart=begin;
            }
            // when char exists in t, increase the counter
            if (++hist[s[begin++]]>0) cnt++;
        }
    }
    return minLen<INT_MAX?s.substr(minStart, minLen) : "";
}

int main()  
{ 
    FAST_INP;
    int t;
    string s;
    cin >> t;
    while(t--){
        cin >> s;
        string ans = helper(s,"123");
        cout << ans.size() << "\n";
    }
    return 0;
} 


/*
LeetCode - Minimum Window Substring

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

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:

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

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> m;
        for(char c:t) m[c]++;
        int cnt=t.size(),begin=0,end=0,minStart=0,minLen=INT_MAX;
        // move end pointer to locate a valid window
        while(end<s.size()){
            // if the char s[end] exists in the map, decrease the counter   
            // decrease m[s[end]], if char doesn't exist, m[s[end]] will be negative
            if(--m[s[end++]]>=0) cnt--;
            // cnt==0 means the window is valid
            while(cnt==0){
                // move start pointer to locate a smaller window
                if(end-begin<minLen){
                    minLen=end-begin;
                    minStart=begin;
                }
                // when char exists in t, increase the counter
                if(++m[s[begin++]]>0) cnt++;
            }
        }
        return minLen<INT_MAX?s.substr(minStart,minLen):"";
    } 
};

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

πŸ† A Collection of my LeetCode Solutions with Explanations πŸ†

GitHub logo wingkwong / hackerrank

πŸ† A Collection of my HackerRank Solutions with Explanations πŸ†

GitHub logo wingkwong / codeforces

πŸ† A Collection of my Codeforces Solutions with Explanations πŸ†

GitHub logo wingkwong / atcoder

πŸ† A Collection of my AtCoder Solutions with Explanations πŸ†

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

pic
Editor guide