# Daily Coding Challenge #8

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

Note:

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

class Solution {
public:
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++) {
m1[s1[i]-'a']++;
m2[s2[i]-'a']++;
}

// 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
m2[s2[i+s1.size()]-'a']++;
// each iteration shifts one character
// uncount index s2[i]-'a' because it will be out of the boundary in the next iteration
m2[s2[i]-'a']--;
}
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 and S, then S and S.

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:

Output: 3
Explanation:
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

Note:

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 {
public:
int numSpecialEquivGroups(vector<string>& A) {
string even,odd;
unordered_set<string> ans;
for(string a:A){
even=odd="";
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(even.begin(),even.end());
// sort odd indexed string
sort(odd.begin(),odd.end());
// combine them together and put it to a set to find the unique groups
ans.insert(even+odd);
}
return ans.size();
}
};
``````

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

## wingkwong / atcoder

### Discussion   