CPP: Palindrom String

Solution for the Palindrom String problem in Cpp

Problem Description

You are given a palindrome string S consisting only of lowercase English letters (a–z).

Examples of palindromes:

aba, aaa, racecar

You may rearrange the characters of the string in any order. Each character can be used at most once.

Your task is to determine the maximum number of three-letter palindromes that can be formed using the letters of the string.

A three-letter palindrome has the structure:

x y x

Where:

  • The first and last characters are the same.
  • The middle character can be any letter.
  • All characters must come from the original string.
  • Each character can be used only once across all palindromes.

If it is not possible to form any three-letter palindrome, return 0.

Example

  • Input: S = "aaaabc" and the Output: 2 because: aba, aca
  • Input: S = "xyvzwy" and the Output: 1 because yxy
  • Input: S = "fknfkn" and the Output: 2 because fkf, nkn

Solution

cpp 
// you can use includes, for example:
// #include <algorithm>
#include <unordered_map>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // Implement your solution here

	// Target: 
	// Return the number of possible 3 letter palindrome
	
	// for "xyvzwy" we should return 1
	// for "fknfkn" we should return 2
	
	// Thinking:
	// We need to count the number of single and pairs charachters.
	// Put it in hash table and increment if found and add if not.
	// Check for every pair has a single char (the 3 palindrome)
	// return the number of possible sub palindrome

	unsigned int num_palindrome_strings = 0;
	
	// because it is using the hash table O(1) access
	std::unordered_map<char, int> M;
	
	for (auto& c : S) {
		if (M.find(c) != M.end()){
			M[c]++;
		} else {
			M[c] = 1;
		}
	}	
	
	// check for every pair has a single char
	// to get the total pairs and singles
	unsigned int pairs = 0, singles = 0;
	
	for (auto& m : M) {
		if (m.second >= 2) {
			// check for odd
			singles += m.second % 2;
			// check for even
			pairs += m.second / 2;
		} else {
			singles++;
		}
	}
	
	// calculate the number of palindrome strings (3 char)
	// so the string size has to be at least 3 char
	// and at least 2 pairs and 1 single or 3 pairs
	
	while (pairs > 0) {
		// check for singles
		if (singles >= 1) {
			// so at least there is 1 pair and 1 single
			num_palindrome_strings++;
			singles--;
			pairs--;
		
		} else {
			// no singles but maybe 3 pairs or more
			if (pairs >= 2) {
				pairs--;
				singles += 2;
				
				num_palindrome_strings++;
				singles--;
				pairs--;
			} else {
				// only 2 pairs
				break;
			}
		}
	}
	
	// of num_palindrome_string = std::min(pairs, (int)S.size() / 3);
	
	return num_palindrome_strings;
}