Home > Reflections | ⏮️ ⏭️

2024-06-03

🧠 Education

🎩 Biomedical Scientist Answers Pseudoscience Questions From Twitter | Tech Support | WIRED

🏋️ Practice

409. Longest Palindrome
This was today’s (Easy) problem of the day.

/* length of longest palindrome possible from scrambling input letters. case sensitive  
Thoughts  
- a palindrome can have  
  - a single unique character (in the middle)  
  - any number of pairs of characters  
- if I find all the unique characters, I can discard all but one of them and keep everything else  
- well... not exactly, I need to discard the odd member of odd numbered sets of characters  
- so if I were to count the frequency of each character...  
  - I could keep a single odd set  
  - then round all the other odd sets down to the nearest even number  
  - keep all the even sets  
  - sum all the numbers  
- this approach would take O(N) time  
  
Plan  
0. create a map to hold frequency counts  
1. scan the string left to right  
  a. for each character, increment the count of that character in the map  
2. collect all odd sized sets  
3. the number of characters I need to discard (D) is the number of odd sets minus one  
4. return s.length - D  
[6:37] finished plan  
[9:51] finished initial implementation  
[16:28] finished testing, submitted solution, success on first try  
bugs identified during testing:  
1. oddCounts was initially the array and not the length of the array, but I treated it like a number  
  - indeed, it's still required to avoid the following error message:  
  `Line 56: Char 28: error TS2339: Property 'filter' does not exist on type 'IterableIterator<any>'.`  
2. I wasn't 100% sure if I needed to do Array.from for map.values(), but I added this in after testing  
*/  
function longestPalindrome(s: string): number {  
  // 1. s=''  
  // 2. s='a'  
  // 3. s='abbccc'  
  const map = new Map()  
  for (let i = 0; i < s.length; i++) {  
    const c = s[i]  
    // 2.1 c=a  
    // 3.1 c=a  
    // 3.2 c=b  
    // 3.3 c=b  
    // 3.4 c=c  
    // 3.5 c=c  
    // 3.6 c=c  
    map.set(c, (map.get(c) || 0) + 1)  
    // 2.1 map={a:1}  
    // 3.1 map={a:1}  
    // 3.2 map={a:1,b:1}  
    // 3.3 map={a:1,b:2}  
    // 3.4 map={a:1,b:2,c:1}  
    // 3.5 map={a:1,b:2,c:2}  
    // 3.6 map={a:1,b:2,c:3}  
  }  
  const counts = Array.from(map.values())  
  // 1. counts=[]  
  // 2. counts=[1]  
  // 3. counts=[1,2,3]  
  const oddCounts = counts.filter(x => x % 2 === 1).length  
  // 1. oddCounts=0  
  // 2. oddCounts=1  
  // 3. oddCounts=2  
  const discard = oddCounts > 1 ? (oddCounts - 1) : 0  
  // 1. discard=0  
  // 2. discard=0  
  // 3. discard=1  
  return s.length - discard  
  // return 0-0=0  
  // return 1-0=1  
  // return 6-1=5  
};