loading...

Daily Coding Challenge #11

wingkwong profile image Wing-Kam ・2 min read

Daily Coding Challenge (80 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 78 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55 56) Daily Coding Challenge #56 57) Daily Coding Challenge #57 58) Daily Coding Challenge #58 59) Daily Coding Challenge #59 60) Daily Coding Challenge #60 61) Daily Coding Challenge #61 62) Daily Coding Challenge #62 63) Daily Coding Challenge #63 64) Daily Coding Challenge #64 65) Daily Coding Challenge #65 66) Daily Coding Challenge #66 67) Daily Coding Challenge #67 68) Daily Coding Challenge #68 69) Daily Coding Challenge #69 70) Daily Coding Challenge #70 71) Daily Coding Challenge #71 72) Daily Coding Challenge #72 73) Daily Coding Challenge #73 74) Daily Coding Challenge #74 75) Daily Coding Challenge #75 76) Daily Coding Challenge #76 77) Daily Coding Challenge #77 78) Daily Coding Challenge #78 79) Daily Coding Challenge #79 80) Daily Coding Challenge #80

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 🏆

Daily Coding Challenge (80 Part Series)

1) Daily Coding Challenge #1 2) Daily Coding Challenge #2 3 ... 78 3) Daily Coding Challenge #3 4) Daily Coding Challenge #4 5) Daily Coding Challenge #5 6) Daily Coding Challenge #6 7) Daily Coding Challenge #7 8) Daily Coding Challenge #8 9) Daily Coding Challenge #9 10) Daily Coding Challenge #10 11) Daily Coding Challenge #11 12) Daily Coding Challenge #12 13) Daily Coding Challenge #13 14) Daily Coding Challenge #14 15) Daily Coding Challenge #15 16) Daily Coding Challenge #16 17) Daily Coding Challenge #17 18) Daily Coding Challenge #18 19) Daily Coding Challenge #19 20) Daily Coding Challenge #20 21) Daily Coding Challenge #21 22) Daily Coding Challenge #22 23) Daily Coding Challenge #23 24) Daily Coding Challenge #24 25) Daily Coding Challenge #25 26) Daily Coding Challenge #26 27) Daily Coding Challenge #27 28) Daily Coding Challenge #28 29) Daily Coding Challenge #29 30) Daily Coding Challenge #30 31) Daily Coding Challenge #31 32) Daily Coding Challenge #32 33) Daily Coding Challenge #33 34) Daily Coding Challenge #34 35) Daily Coding Challenge #35 36) Daily Coding Challenge #36 37) Daily Coding Challenge #37 38) Daily Coding Challenge #38 39) Daily Coding Challenge #39 40) Daily Coding Challenge #40 41) Daily Coding Challenge #41 42) Daily Coding Challenge #42 43) Daily Coding Challenge #43 44) Daily Coding Challenge #44 45) Daily Coding Challenge #45 46) Daily Coding Challenge #46 47) Daily Coding Challenge #47 48) Daily Coding Challenge #48 49) Daily Coding Challenge #49 50) Daily Coding Challenge #50 51) Daily Coding Challenge #51 52) Daily Coding Challenge #52 53) Daily Coding Challenge #53 54) Daily Coding Challenge #54 55) Daily Coding Challenge #55 56) Daily Coding Challenge #56 57) Daily Coding Challenge #57 58) Daily Coding Challenge #58 59) Daily Coding Challenge #59 60) Daily Coding Challenge #60 61) Daily Coding Challenge #61 62) Daily Coding Challenge #62 63) Daily Coding Challenge #63 64) Daily Coding Challenge #64 65) Daily Coding Challenge #65 66) Daily Coding Challenge #66 67) Daily Coding Challenge #67 68) Daily Coding Challenge #68 69) Daily Coding Challenge #69 70) Daily Coding Challenge #70 71) Daily Coding Challenge #71 72) Daily Coding Challenge #72 73) Daily Coding Challenge #73 74) Daily Coding Challenge #74 75) Daily Coding Challenge #75 76) Daily Coding Challenge #76 77) Daily Coding Challenge #77 78) Daily Coding Challenge #78 79) Daily Coding Challenge #79 80) Daily Coding Challenge #80

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide