Q1. Longest palindrome

1. Even length:
2. odd length: single additional character is counted in the middle

Intuition:

• find out how many times each character appears in s

→ hash table: good way to count the frequency → each character is key and frequency is the value

Algorithm(Greedy hashtable):

• initialize the map frequencyMap to store the frequency of each character
• count the frequency of each character in given string
• initialize variables:
  • res: store the length of the longest palindrome
  • hasOddFrequency: flag to check whether a character with odd frequency exists
• Loop through the frequencies freq of each character:
  • If freq even, add it to res
  • if freq is odd, add freq-1 to res and set hasOddFrequency to true
• If hasOddFrequency is true, return res+1, otherwise return res

class Solution{
	public int longestPanlidrome(String s){
		// Map to store freqnency of occurence of each charater
		Map<Character, Integer> frequencyMap = new HashMap<>();
		// Count frequencies
		for(char c : s.toCharArray()){
				frequencyMap.put(c, frequencyMap.getOrDefault(c,0) + 1)
		}
		
		int res = 0;
		boolean hasOddFrequency = false;
		// freq = values of hashmap
		for (int freq : frequencyMap.values()){
				//check if frequency is even
				if((freq % 2) == 0){
						res += freq;
				} else{
						res += freq - 1;
						hasOddFrequency = true;
				}
		}
		// If hasOddFrequency is true, we have at least one unmatched
		// character to make the center of a odd length palidrome
		if(hasOddFrequency) return res + 1;
		
		return res;
	}
}

Merge sorted array

With two given integer arrays num1 and num2 sorted in non-decreasing order

m,n represent the number of elements in nums1 and nums2

final sorted array should not be returned by the function, but instead be stored in the arrary nums1, length n+m

repetition should be counted

• if length of m or n is 1 or zero
  • m is 1, do nothing return void
  • n is 1 set the nums1 = nums2
  • both zero → return