- Prepare
- Algorithms
- Strings
- Game of Thrones - I
- Discussions
Game of Thrones - I
Game of Thrones - I
+ 36 comments If you are stuck you can follow this logic:
If len(str) is even, count of each elemnt should be even.
If len(str) is odd, count of ONLY one element should be odd, counts of all other elements should be even.
+ 5 comments But the Dothraki never cross the seas. How did they invade Westeros?
I kid.. I kid
+ 2 comments bit shifting is fun :)
int main() { string s; cin>>s; int flag = 0; uint64_t mask = 0x0; for (int i = 0; i < s.length(); i++) mask = mask ^ (1 << (s[i]-'a')); if ((!mask) || (((mask & (mask - 1)) == 0))) flag = 1; if(flag==0) cout<<"NO"; else cout<<"YES"; return 0; }
+ 0 comments C++ solution...
string gameOfThrones(string s) { vector<int> f(26,0); for(int i=0;i<s.size();i++) { f[s[i]-'a']++; } int count1=0; for(int i=0;i<26;i++) { if(f[i]%2!=0&&count1==1) return "NO"; if(f[i]%2!=0) count1++; } return "YES"; }
+ 2 comments Here's a more in-depth explanation of the counting solution.
The problem asks you to divide a string into two mirrored parts. For example:
[abababab]
[aabb][bbaa]
A letter in the string can appear an odd or an even number of times. Let's consider what happens when the number of letters that appears an odd number of times varies.
0 "odd letters":
[aabbaabb]
[----][----]
Each letter on the left side must have a pair on the right side. If the number is even, it means we can definitely divide this string into two mirrored parts, as each letter does have a pair.
1 "odd letters":
[aabbaabbccc]
[----]ccc[----]
c[----]c[----]c
When we have 1 "odd" letter, the string can only be a palindrome if the letter without a pair is in the middle, between the two mirrored parts. Therefore, we can make a palindrome in this case.
2 or more "odd letters":
[aabbaabbcccddd]
[----]ccc[----]
c[----]c[----]c
In the case of one "odd" letter, we can put the unpaired one in the middle. But we only have one middle, so if the number of "odd" letters is any higher than 1, there is no possible position we can put the second "odd" letter and still have the string be a palindrome.
Sort 920 Discussions, By:
Please Login in order to post a comment