Brainstorming Quiz - Day 3 Solution

String: AdaTreFeRsraDAReMaDaMfDeIfIeDhLeVeLcStAtSemUrdrUMtADA

Answer: TECHFEST

Explanation of the Approach:

To decode the given message, the string consists of alternating palindromic substrings and non-palindromic segments. The decoding process involves the following steps:

1. Extract Palindromes and Non-Palindromic Strings:
   • Identify palindromic substrings in the string step-by-step, skipping characters after each palindrome.
   • Collect non-palindromic segments that appear between the palindromic substrings.
2. Concatenate the Non-Palindromic Segments:
   • Gather all non-palindromic strings into a single concatenated result.
3. Reverse the Non-Palindromic String:
   • Reverse the concatenated non-palindromic string to reveal the decoded message.

This approach ensures that the alternating structure of palindromes and normal strings is utilized to extract the hidden message effectively.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// Function to check if a substring is a palindrome
bool isPalindrome(const string &str, int start, int end)
{
  while (start < end)
  {
    if (str[start] != str[end])
      return false;
    start++;
    end--;
  }
  return true;
}

// Function to find the longest palindrome substring starting at currentIndex
string findPalindrome(const string &str, int &currentIndex)
{
  int n = str.size();
  string longestPalindrome = "";

  for (int end = currentIndex + 1; end <= n; end++)
  {
    if (isPalindrome(str, currentIndex, end - 1))
    {
      string palindrome = str.substr(currentIndex, end - currentIndex);
      if (palindrome.size() > longestPalindrome.size())
      {
        longestPalindrome = palindrome;
      }
    }
  }

  if (!longestPalindrome.empty())
  {
    currentIndex += longestPalindrome.size(); // Skip the palindrome
    return longestPalindrome;
  }

  return ""; // No palindrome found
}

int main()
{
  string input = "AdaTreFeRsraDAReMaDaMfDeIfIeDhLeVeLcStAtSemUrdrUMtADA";

  // Convert string to uppercase
  transform(input.begin(), input.end(), input.begin(), ::toupper);
  cout << "Converted to uppercase: " << input << endl;

  int currentIndex = 0;          // Start index for searching
  string result = "";            // To store all palindromes
  string singlePalindromes = ""; // To store single-character palindromes

  while (currentIndex < input.size())
  {
    string palindrome = findPalindrome(input, currentIndex);
    if (!palindrome.empty())
    {
      result += palindrome + " ";
      if (palindrome.size() == 1)
      {
        singlePalindromes += palindrome;
      }
    }
    else
    {
      // No more palindromes, break out of the loop
      break;
    }
  }

  // Reverse the single-character palindromes string
  string reversedSinglePalindromes = singlePalindromes;
  reverse(reversedSinglePalindromes.begin(), reversedSinglePalindromes.end());

  // Log the concatenated and reversed single-character palindromes
  cout << "Non palindrome string: " << singlePalindromes << endl;
  cout << "Decoded message: " << reversedSinglePalindromes << endl;

  return 0;
}