palindrome-free-strings-google-kickstart.js

// 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.

/** For checking if a string is palindrom or not */
function isPalindrome(string) {
  return string == string.split("").reverse().join("");
}

/** Generating all the substrings and checking if they are palindromes */
function getAllPalindromeSubstrings(str) {
  var i,
    j,
    result = [];

  for (i = 0; i < str.length; i++) {
    for (j = i + 1; j < str.length + 1; j++) {
      var subString = str.slice(i, j);
      if (subString.length > 4 && isPalindrome(subString)) {
        result.push(subString);
      }
    }
  }
  return result;
}

/** Get all combinations of a string as per the problem statement */
function getAllCombinations(str) {
  var combos = [];

  var processedStr = "";
  if (str.length === 0) return [""];
  var toBeProcessedStr = str.slice(1);

  var toBeConcatted =
    toBeProcessedStr.indexOf("?") > -1
      ? getAllCombinations(toBeProcessedStr)
      : [toBeProcessedStr];

  if (str[0] !== "?") {
    for (var i = 0; i < toBeConcatted.length; i += 1) {
      var replacedWithNone = processedStr.concat(str[0], toBeConcatted[i]);
      combos.push(replacedWithNone);
    }
  } else {
    for (var i = 0; i < toBeConcatted.length; i += 1) {
      var toBeConcattedStr = toBeConcatted[i];
      var replacedWith0 = processedStr.concat("0", toBeConcattedStr);
      var replacedWith1 = processedStr.concat("1", toBeConcattedStr);
      combos.push(replacedWith0);
      combos.push(replacedWith1);
    }
  }
  return combos;
}

/** Checking whether the input string is passed as per the problem statement */
function isPossible(problem) {
  for (var j = 0; j < problem.testCases.length; j += 1) {
    const str = problem.testCases[j];

    var possibleStrings = getAllCombinations(str);
    var noPalindromExists = false;
    for (var i = 0; i < possibleStrings.length; i += 1) {
      var possiblePalindromes = getAllPalindromeSubstrings(possibleStrings[i]);
      if (possiblePalindromes.length === 0) {
        noPalindromExists = true;
        break;
      }
    }
    console.log(`Case #${j}: ${noPalindromExists ? "POSSIBLE" : "IMPOSSIBLE"}`);
  }
}

/** Get the input */
function readInput() {
  const readline = require("readline");
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false,
  });

  let problem = {
    T: 0,
    testCases: [],
  };
  let inputsCount = 1;

  rl.on("line", function (line) {
    if (problem.T === 0) {
      // Get number of test cases from first line
      problem.T = Number(line);
    } else {
      if ((inputsCount - 1) % 2 === 0) {
        problem.testCases.push(line);
      }
    }
    inputsCount += 1;
  }).on("close", () => {
    isPossible(problem);
    process.exit();
  });
}

readInput();