FAULTYKBD - Editorial

Practice
Contest Source
Author, Tester and Editorialist : Rohail Alam

DIFFICULTY:

Easy

PREREQUISITES:

Implementation

PROBLEM:

Given a string, you are asked to print all non-unique characters of every (non-overlapping) five-sized sub-string.

EXPLANATION:

For every five characters of the given string, you need to keep tabs of what characters have already occurred before, and store the characters that are being repeated.

This can be implemented using an STL set in C++ or even with a Python set (as it stores unique values). The characters of the string will be continuously inserted into the set and will be cleared for every fifth character typed (as the condition is reset). If the current character is already present in the set, it will be a part of our answer (since it has been typed once already)

Taking an example - "aaaab "
If we consider the first five characters - “aaaab” , the output obtained will be "aaa" as:

  • The first character ‘a’ is not recorded (as it isn’t present in the set which is currently empty)
  • The next three ‘a’ characters are recorded (as ‘a’ is present in the set)
  • The fifth character ‘b’ is not recorded (as ‘b’ is not present in the set)

TIME COMPLEXITY:

O(n . log(n))

SOLUTION:

C++ Solution
#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string s;
        cin>>s;
        set<char> vals;
        string ans = "";
        for(int i=0;i<(int)s.size();++i){
            if(i%5 == 0) vals.clear();
            if(vals.count(s[i])){
                ans+=s[i];
            }
            vals.insert(s[i]);
        }
        cout<<ans<<endl;
    }
}