1.4. Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards.
The first solution is with hashmap:
Let's revise bit vectors and here is the next solution:
For a string to be a palindrome permutation, all letters must appear even number of times, but at most one letter can appear odd number of times (the middle one). With XOR operator, each time a character appears we flip its bit:
Even occurrences ➡️ bit ends up as 0
Odd occurrences ➡️ bit ends up as 1
At the end:
If all bits are 0 ➡️ every letter appears even times.
If exactly one bit is 1 ➡️ only one letter appears odd times.
To check the latter case, we use bitmask. if there is one 1 bit in integer, like 00010000, we subtract 1 then it becomes 00001111. after applying AND operator it will be 0, that confirms exactly one bit was set.
#crackingthecodinginterview
The first solution is with hashmap:
public static boolean f1(String s) {
Map<Character, Integer> map = new HashMap<>();
int oddFrequencies = 0;
for (char ch : s.toCharArray()) {
if (!Character.isLetter(ch)) continue;
ch = Character.toLowerCase(ch);
map.put(ch, map.getOrDefault(ch, 0) + 1);
if (map.get(ch) % 2 != 0) oddFrequencies++;
else oddFrequencies--;
}
return oddFrequencies <= 1;
}
// TC - O(n)
// SC - O(n)Let's revise bit vectors and here is the next solution:
public static boolean f2(String s) {
int bits = 0;
for (char ch : s.toCharArray()) {
if (!Character.isLetter(ch)) continue;
int k = Character.toLowerCase(ch) - 'a';
bits ^= (1 << k);
}
return bits == 0 || (bits & (bits - 1)) == 0;
}
// TC - O(n)
// SC - O(1)For a string to be a palindrome permutation, all letters must appear even number of times, but at most one letter can appear odd number of times (the middle one). With XOR operator, each time a character appears we flip its bit:
Even occurrences ➡️ bit ends up as 0
Odd occurrences ➡️ bit ends up as 1
At the end:
If all bits are 0 ➡️ every letter appears even times.
If exactly one bit is 1 ➡️ only one letter appears odd times.
To check the latter case, we use bitmask. if there is one 1 bit in integer, like 00010000, we subtract 1 then it becomes 00001111. after applying AND operator it will be 0, that confirms exactly one bit was set.
#crackingthecodinginterview
⚡4
image_2025-12-16_00-53-41.png
21.3 KB
#N1679. Max Number of K-Sum Pairs
problem link
#solution
TC - O(n)
SC - O(n)
problem link
#solution
TC - O(n)
SC - O(n)
class Solution {
public int maxOperations(int[] nums, int k) {
int count = 0;
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
if(map.containsKey(n)){
count++;
map.put(n, map.get(n) -1);
if(map.get(n)==0) map.remove(n);
}else if(n<k){
map.put(k-n, map.getOrDefault(k-n, 0) +1);
}
}
return count;
}
}