4
\$\begingroup\$

The task:

Given a string which we can delete at most k, return whether you can make a palindrome.

For example, given 'waterrfetawx' and a k of 2, you could delete f and x to get 'waterretaw'.

The following solution is partially inspired by @Oh My Goodness's answer.

const s = "waterrfetawx";
const del = 2;

function palindromePossible(str, deleteAtMost) {
  const set = new Set();
  for (let i = 0, len = str.length; i < len; i++) {
    const char = str[i];
    void(set.delete(char) || set.add(char)); // <--is this good code?
  }

  let iStart = 0, iEnd = str.length - 1, possibleDeletion = 0;

  function isSame() {
    do {
      if (str[iStart] === str[iEnd]) {
        iStart++;
        iEnd--;
        return true;
      }
      if (++possibleDeletion > deleteAtMost) { return false; }
      if (set.has(str[iStart])) { iStart++; }
      if (set.has(str[iEnd])) { iEnd--; }
      if (iStart > iEnd) { return false; }
    } while(str[iStart] !== str[iEnd]);

    return true;
  }

  if (set.size <= deleteAtMost + 1) {
    for (let i = 0, len = Math.floor(str.length/2); i < len && iStart <= iEnd; i++) {
      if (!isSame()) { return false; }
    }
    return true;
  }
  return false;
}

console.log(palindromePossible(s, del));
\$\endgroup\$
  • \$\begingroup\$ I think you might have an off-by-1 error? palindromePossible("waterrfetawx", 1) returns true. AKA shouldn't deleteAtMost + 1 just be deleteAtMost? \$\endgroup\$ – Shelby115 Apr 8 at 19:22
  • \$\begingroup\$ You can re-order it like this waterfretawx and then delete the x. waterfretaw can the be read forward and backwards @Shelby115 \$\endgroup\$ – thadeuszlay Apr 8 at 19:26
  • \$\begingroup\$ Ah, wasn't aware that re-ordering it was an option. \$\endgroup\$ – Shelby115 Apr 8 at 19:27
  • \$\begingroup\$ but good point. I will think of an algorithm that doesn't take re-ordering into consideration. @Shelby115 \$\endgroup\$ – thadeuszlay Apr 8 at 19:30
  • 1
    \$\begingroup\$ I think that allowing reordering is a bit of a cheat, especially if it is not mentioned in the task and the example lets you believe it isn't allowed. The given solutions don't work if it is not allowed. \$\endgroup\$ – KIKO Software Apr 8 at 19:35
2
\$\begingroup\$

You have a question embedded in the code:

void(set.delete(char) || set.add(char)); // <--is this good code?

The void operator "evaluates the given expression and then returns undefined"1. It doesn't appear that there is a need to have undefined be the final value of that expression because that expression doesn't get assigned or returned. The void() can be removed without changing the functionality of the code. I wouldn't say it is bad code, but unnecessary.


That for loop could be simplified:

for (let i = 0, len = str.length; i < len; i++) {
  const char = str[i];
  void(set.delete(char) || set.add(char)); // <--is this good code?
}

using a for...of loop:

for (const char of str) {
  set.delete(char) || set.add(char);
}

1https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/void

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.