Palindrome Free Strings – My solution in C++

I took this problem from Google Kickstart 2022, round A. This one is a truly interesting problem to challenge our understanding of dynamic programming. Out of around 17.5k participants, there are only 654 participants, just around 4% of all, who can solve this problem. To be honest, this 4% would not include me if I joined at the time.

The problem

You are given a string \(S\) consisting of characters 0, 1, and ?. You can replace each ? with either 0 or 1. Your task is to find if it is possible to assign each ? to either 0 or 1 such that the resulting string has no substrings that are palindromes of length 5 or more.

Input The first line of the input gives the number of test cases, \(T\). \(T\) test cases follow. Each test case consists of two lines. The first line of each test case contains an integer \(N\), denoting the length of the string \(S\). The second line of each test case contains a string \(S\) of length \(N\).

Output For each test case, output one line containing Case #\(x\): \(y\), where \(x\) is the test case number (starting from 1) and \(y\) is POSSIBLE if there is a possible resulting string that has no palindromic substrings of length 5 5 or more, or IMPOSSIBLE otherwise.

Limits

Memory limit: 1 GB.

\(1\leq T\leq 100\).

\(S\) only consists of characters 0, 1 and ?.

Test Set 1

Time limit: 20 seconds.

\(1\leq N\leq 15\).

Test Set 2

Time limit: 90 seconds.

\(1\leq N\leq 5\times 10^4\).

My thoughts

First I imagine a string that contains a palindrome of length more than 5, to check if all strings like that could be avoided. As about palindromes, there are two cases: the ones that have odd lengths (Ex: 00100), and the ones that have even lengths (Ex: 0110). The question says “palindromes of length 5 or more”. Even if the palindrome has a length of 7, it would still contain a length-5 palindrome, and so does the parent string. Therefore, we would only need to care about length-5 (for the odd lengths) and length-6 (for the even lengths) palindromes of any given string.

Now the problem looks more like backtracking. For any given string, we go from the start of the string to the end, by advancing the pointer 1 character ahead, and check for the length-5 and length-6 palindromes. With the “?”s we create different paths to check out. If there is a palindrome, then the path is incorrect, we back and try another one. If there is no path to go from start to end, then the result is impossible. Otherwise, the result is possible. Looks like the problem is solved. We are almost there, I thought.

Let us try out this strategy on the sample problem: 100???001

of which the correct solution is Case #1: IMPOSSIBLE

At the first glance, the first 5 characters contain two “?”s. This is something I haven’t thought about. There should be an initial step to create the initial strings which match the pattern “100??” before we can move on. I wrote this step inside the function generateInitialStrings. That was not the best name but we are thinking fast lol… Now we have 4 paths to check:

10000

10001

10010

10011

All good! Out of the four paths, we ignore the second one “10001” since it is a palindrome. Now we proceed with the other 3. The next character in the pattern string is again “?”. Therefore, we have \(3\times2=6\) possible paths ahead:

100000

100001

10001

100100

100101

100110

100111

Now we can check for length-5 and length-6 palindromes. The first one contains a length-5 palindrome “00000”. It ends there. The same goes for the second one since it contains a length-6 palindrome “100001”. The procedure goes on. And there will not be any missing length-5 or length-6 palindromes which are not checked. The procedure terminates in 2 cases: when we are in the middle of the pattern string and there are no paths to go forward, OR we end up at the end of the pattern string.

Thinking about much longer strings that have “?”s at the beginning and 0/1 after that. In such a case, there will be many duplicates of checks at one later position, if there are many possibilities to go forward from the beginning. We can avoid this by having a hash map, isDone, which marks if the same path has already been added to the stack. The key of a term in isDone, for example, can contain the nearest five characters (which are the only ones that matter), and the index of the next element in the pattern string to check out. Potentially, we can avoid a lot of computation, since if there is a new “?” to proceed, there will be \(2\times\)NS paths to check out, where NS is the number of function calls in the stack queue at that “?”. The number of total paths to checkout can then be in the order of \(2^{\text{number of "?"}}\). This hash map limits the total number of function calls to \(2^5(N-4)\).

Check out my solution below and let me know if you have better ideas to solve this problem.

Full solution in C++17

#include <iostream>
#include <map>
#include <vector>

#define int long long

std::vector<std::string> generateInitialStrings(std::string str) {
  std::vector<std::string> allStrings;
  if (str[0] == '?') {
    allStrings.push_back("0");
    allStrings.push_back("1");
  } else {
    std::string firstLetter(1, str[0]);
    allStrings.push_back(firstLetter);
  }
  for (int i = 1; i < str.length(); i++) {
    if (str[i] == '?') {
      int numAllStrings = allStrings.size();
      for (int j = 0; j < numAllStrings; j++) {
	allStrings.push_back(allStrings[j]+"1");
	allStrings[j] += "0";
      }
    } else {
      for (int j = 0; j < allStrings.size(); j++) {
	allStrings[j] += str[i];
      }
    }
  }
  return allStrings;
}

bool isPalindrome(std::string str) {
  int length = str.length();
  for (int i = 0; i < length/2; i++)
    if (str[i] != str[length-1-i])
      return false;
  return true;
}

void checkIfPalindromeFree(std::string & S,
			 std::string str,
			 int nextIndex,
			 std::map<std::pair<std::string, int>, int> & isDone,
			 bool & result) {
  if (nextIndex >= S.length()) {
    if (!isPalindrome(str))
      result = true;
  } else {
    auto pair = std::make_pair(str, nextIndex);
    if (isDone.count(pair) == 0) {
      isDone[pair] = 1;
      if (!isPalindrome(str)) {
	if (S[nextIndex] == '?') {
	  if (!isPalindrome(str + "0"))
	    checkIfPalindromeFree(S, str.substr(1) + "0", nextIndex+1, isDone, result);
	  if (!isPalindrome(str + "1"))
	    checkIfPalindromeFree(S, str.substr(1) + "1", nextIndex+1, isDone, result);
	} else
	  if (!isPalindrome(str + S[nextIndex]))
	    checkIfPalindromeFree(S, str.substr(1) + S[nextIndex], nextIndex+1, isDone, result);
      }
    }
  }
  return;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int numCases;
  std::cin >> numCases;

  for (int caseNum = 1; caseNum <= numCases; caseNum++) {
    int N;
    std::cin >> N;
    std::string S;
    std::cin >> S;

    std::map<std::pair<std::string, int>, int> isDone;

    bool result = false;
    if (N >= 5) {
      std::vector<std::string> initialStrings = generateInitialStrings(S.substr(0, 5));
      for (int i = 0; i < initialStrings.size(); i++)
        checkIfPalindromeFree(S, initialStrings[i], 5, isDone, result);
    } else
      result = true;
    
    std::string resultTxt = result ? "POSSIBLE" : "IMPOSSIBLE";
    std::cout << "Case #" << caseNum << ": " << resultTxt << std::endl;
  }

  return 0;
}