Coding Interview Questions | Longest Palindrome

December 29th, 2023

Longest Palindrome Palindrome Introduction:

This summary will talk about my solution to the longest palindrome problem as seen on leetcode here.

Longest Palindrome Solution:

function longestPalindrome(s: string): number {
  const charCountMap = new Map<string, number>();

  // Populate char count map with counts of each character
  for (const char of s) {
    const currentCharCount = charCountMap.get(char) ?? 0;
    charCountMap.set(char, currentCharCount + 1);
  }

  let longestPalindromeCount = 0;
  const charCountedSet = new Set();
  for (const char of s) {
    const currentCharCount = charCountMap.get(char)!;

    // Even character counts can always create a palindrome
    if (currentCharCount % 2 === 0) {
      // Don't add count if a character has already been counted
      if (charCountedSet.has(char)) {
        continue;
      }
      longestPalindromeCount += currentCharCount;

      charCountedSet.add(char);
    }
  }

  let longestOddCharacter: { letter: string; count: number } = {
    letter: "a",
    count: 0,
  };
  for (const char of s) {
    const currentCharCount = charCountMap.get(char)!;
    if (currentCharCount % 2 === 1) {
      if (currentCharCount > longestOddCharacter.count) {
        longestOddCharacter = { count: currentCharCount, letter: char };
      }
    }
  }

  for (const char of s) {
    const currentCharCount = charCountMap.get(char)!;

    // Check odd characters
    if (currentCharCount % 2 !== 0) {
      // Don't add count if a character has already been counted
      if (charCountedSet.has(char)) {
        continue;
      }

      if (char === longestOddCharacter.letter) {
        longestPalindromeCount += currentCharCount;
      } else {
        longestPalindromeCount += currentCharCount - 1;
      }

      charCountedSet.add(char);
    }
  }

  return longestPalindromeCount;
}

Longest Palindrome Problem Summary:

• Character Count Map:

  • A Map (charCountMap) is initialized to store the count of each character in the input string.

• Even Count Palindromes:

  • We iterate through the characters in the string, adding the count of characters with even occurrences to the result (longestPalindromeCount).

• Handling Odd Counts:

  • We identify the character with the maximum odd count and keep track of it.
  • We iterate through the string again, adding the count for characters with odd occurrences, ensuring that if the character being counted is not the character with the longest odd count, we only track the character count - 1 to the palindrome length.

• Final Result:

  • After this iteration is complete, we return the calculated longestPalindromeCount as the length of the longest palindrome that can be formed with the given characters.

• Complexity:

  • The solution has a time complexity of O(N), where N is the length of the input string, as we only iterate over the string linearly.
  • We use additional data structures (Map, Set) for efficient character counting and tracking. The space complexity of the solution is O(1) however, as at most there are 52 characters that could be stored in the Map or Set (given upper and lower case letters), and because that value is constant, the overall space complexity is a constant as well.

Bonus Solution:

function longestPalindrome(s: string): number {
  const charCount = Array.from({ length: 128 }, () => 0); // Assuming ASCII characters

  for (const char of s) {
    charCount[char.charCodeAt(0)]++;
  }

  let longestPalindromeCount = 0;
  let hasOddCharacter = false;

  for (const count of charCount) {
    longestPalindromeCount += Math.floor(count / 2) * 2;

    if (count % 2 === 1) {
      hasOddCharacter = true;
    }
  }

  // If there's at least one character with an odd count, add 1 to the result
  return longestPalindromeCount + (hasOddCharacter ? 1 : 0);
}