267. Palindrome Permutation I

The trick here as the hint says is we only need to track the first half string. So we need to count the number for the first half string. Also, we need to keep the middle character if the string has an odd length. And finally, we need to use hashtable to store each character’s count. After that, the problem becomes a classic backtracking permutation problem.

I used vector as hash table in first place. But I got TLE. I guess it’s too cost to check for 256 characters every time. Also when doing unordered_map, the iterator it in the loop “for (auto it : mp)” is a copy not the real iterator itself. So if you update this copy, it doesn’t change the content of the unordered_map at all. So we need to do either “for (auto &it : mp)” or “for (auto it=mp.begin(); it != mp.end(); i++)”.

1:  class Solution {  
2:  public:  
3:    vector<string> generatePalindromes(string s) {  
4:      unordered_map<char, int> mp;  
5:      vector<string> res;  
6:      for (int i = 0; i < s.size(); i++) {  
7:        mp[s[i]]++;  
8:      }  
9:      int odd = 0, len = 0;  
10:      string mid = "";  
11:      for (auto it = mp.begin(); it != mp.end(); it++) {  
12:        if (it->second & 1) { odd++; mid += it->first; }  
13:        it->second /= 2;  
14:        len += it->second;  
15:      }  
16:      if (odd > 1) return res;  
17:      gen(mp, len, mid, "", res);  
18:      return res;  
19:    }  
20:    void gen(unordered_map<char, int> &mp, int len, string &mid, string s, vector<string> &res) {  
21:      if (s.size() == len) {  
22:        string r = s;  
23:        reverse(r.begin(), r.end());  
24:        res.push_back(s+mid+r);  
25:        return;  
26:      }  
27:      for (auto it = mp.begin(); it != mp.end(); it++) {  
28:        if (it->second > 0) {  
29:          it->second--;  
30:          gen(mp, len, mid, s+it->first, res);  
31:          it->second++;  
32:        }  
33:      }  
34:    }  
35:  };  

266. Palindrome Permutation

I was thinking to traverse the buckets twice. First round is to count the number of each character. The second round is to count the number of odds. If odds is less than 2, return true. Otherwise, return false.
The top rated solution combine the two rounds into one round but actually the same running time.

1:  class Solution {  
2:  public:  
3:    bool canPermutePalindrome(string s) {  
4:      vector<int> chars(256, 0);  
5:      int odd = 0;  
6:      for (char c : s) {  
7:        odd += ++chars[c] & 1 ? 1 : -1;  
8:      }  
9:      return odd < 2;  
10:    }  
11:  };  

3. Longest Substring Without Repeating Characters

This is very similar idea to problem "340. Longest Substring with At Most K Distinct Characters".
1. we keep moving one pointer and count each character until one character has been counted before, i.e. the count for the character is one already.
2. Then we move another pointer and decrease the counter for each character until the character pointed by the first pointer has count 0.
3. And then leave the second pointer there and move the first pointer again. Repeat step 1-2 until the first pointer reaches the end.

1:  class Solution {  
2:  public:  
3:    int lengthOfLongestSubstring(string s) {  
4:      vector<int> chars(256, 0);  
5:      int i = 0, j = 0, maxLen = 0;  
6:      while (i < s.size()) {  
7:        while (i < s.size() && chars[s[i]] == 0) {++chars[s[i++]];};  
8:        maxLen = max(maxLen, i - j);  
9:        while (i < s.size() && chars[s[i]] == 1) --chars[s[j++]];  
10:      }  
11:      return maxLen;  
12:    }  
13:  };