Daily Coding Challenge #8

wingkwong profile image Wing-Kam ・3 min read


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.

LeetCode - Permutation in String
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False


The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

class Solution {
    bool helper(vector<int> &m1, vector<int> &m2){
        for(int i=0;i<26;i++){
            // if they are not the same, return false immediately
            if(m1[i]!=m2[i]) return false;
        return true;

    bool checkInclusion(string s1, string s2) {
        // if s1 size is greater than s2, then it cannot be a substring
        if(s1.size()>s2.size()) return false;
        // use two maps to store the occurrence of each letter 
        vector<int> m1(26,0),m2(26,0);
        // count the occurrence for s1 & s2 for the first window where the size is s1.size() 
        for(int i=0;i<s1.size();i++) {

        // sliding window approach
        for(int i=0;i<s2.size()-s1.size();i++){
            // check if m1 and m2 are the same within the window
            if(helper(m1,m2)) return true;
            // count the occurrence for the next window
            // each iteration shifts one character
            // uncount index s2[i]-'a' because it will be out of the boundary in the next iteration 
        return helper(m1,m2);

Groups of Special-Equivalent Strings

You are given an array A of strings.

A move onto S consists of swapping any two even indexed characters of S, or any two odd indexed characters of S.

Two strings S and T are special-equivalent if after any number of moves onto S, S == T.

For example, S = "zzxy" and T = "xyzz" are special-equivalent because we may make the moves "zzxy" -> "xzzy" -> "xyzz" that swap S[0] and S[2], then S[1] and S[3].

Now, a group of special-equivalent strings from A is a non-empty subset of A such that:

Every pair of strings in the group are special equivalent, and;
The group is the largest size possible (ie., there isn't a string S not in the group such that S is special equivalent to every string in the group)
Return the number of groups of special-equivalent strings from A.

Example 1:

Input: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3
One group is ["abcd", "cdab", "cbad"], since they are all pairwise special equivalent, and none of the other strings are all pairwise special equivalent to these.

The other two groups are ["xyzz", "zzxy"] and ["zzyx"].  Note that in particular, "zzxy" is not special equivalent to "zzyx".
Example 2:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3


1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i] consist of only lowercase letters.

class Solution {
    int numSpecialEquivGroups(vector<string>& A) {
        string even,odd;
        unordered_set<string> ans;
        for(string a:A){
            for(int i=0;i<a.size();i++){
                // construct a string with even indexed characters
                if(i%2==0) even+=a[i];
                // construct a string with odd indexed characters
                else odd+=a[i];
            // sort even indexed string
            // sort odd indexed string
            // combine them together and put it to a set to find the unique groups
        return ans.size();

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



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


Editor guide