This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.

preface

Leetcode’s problem of the day was a little bit easier today, so I found another problem as an exercise.

A daily topic

Today’s lesson of the day is 1332. Deleting a sequence of pheromones is easy

  • You are given the string S, which consists only of the letters ‘a’ and ‘b’. Each deletion removes a palindrome subsequence from S.

  • Returns the minimum number of deletions to delete all empty characters in a given string.

  • “Subsequence” definition: A string is a subsequence of the original string if it can be obtained by deleting some characters from the original string without changing the character order.

  • Palindrome definition: a string is a palindrome if it is read backwards and forwards identically.

From the definition of subsequence, we can know that subsequence does not need to be continuous, which is quite different from substring, and there are only a and B strings, so the worst case is to delete all a as a subsequence first, and then only B is left to delete once, which needs to be deleted twice. The better case is that the string s is a palindrome, so you can delete it. So here we know, our key point is to determine if the string s is a palindrome, which is a little bit easier.

/ * * *@param {string} s
 * @return {number}* /
var removePalindromeSub = function(s) {
    const n = s.length;
    for (let i = 0; i < Math.floor(n / 2); ++i) {
        if(s[i] ! == s[n -1 - i]) {
            return 2; }}return 1;
};
Copy the code

Let’s do a similar problem with a little more difficulty

Since the daily question was a little bit easier, I chose a similar, more difficult question.

5. The longest substring on Leetcode is of medium difficulty

Given a string s, find the longest substring in s.

Example 1:

Enter: s ="babad"Output:"bab"Explanation:"aba"It is also the answer to the question.Copy the code

Example 2:

Enter: s ="cbbd"Output:"bb"
Copy the code

Example 3:

Enter: s ="a"Output:"a"
Copy the code

Example 4:

Enter: s ="ac"Output:"a"
Copy the code

Tip:

  • 1 <= s.length <= 1000
  • S consists of only numbers and English letters (uppercase and/or lowercase)

Answer key

In this problem, notice that the concept of a subsequence is different from the concept of a subsequence in the daily problem, it has to be continuous.

Violent solution

First of all, the first method, the most simple solution to violence, we can go directly to traverse each substring, then use two variables respectively record back to the text string of maximum length and longest back text string, each time to judge whether meet the requirements and then determine whether longer than save the eldest son of string, is replaced, or skip.

/ * * *@param {string} s
 * @return {string}* /
var longestPalindrome = function (s) {
  let ans = "";
  let max = 0;
  let len = s.length;
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j <= len; j++) {
      let test = s.slice(i, j);
      if (isPalindrome(test) && test.length > max) {
        ans = test;
        max = Math.max(max, ans.length); }}}return ans;
};
function isPalindrome(s) {
  let len = s.length;
  for (let i = 0; i < len / 2; i++) {
    if(s[i] ! = s[len - i -1]) {
      return false; }}return true;
}
Copy the code

It can be seen that although ac is successful, it takes a long time to run, so it will be optimized later

The second kind of solution

The second method we convert a train of thought, not necessarily going to traverse each substring, for a string, each character is the center of the string could be a palindrome, so, we can change a train of thought, traversal string, in the process of traverse to record to each center can enlarge the maximum range, finally get the one that is the longest substring.

So we’re going to notice that one point, the center point, could be one character or it could be two characters, so for example, the substring “ABA” is centered on B, but the substring “ABba” is centered on two characters, and it’s centered on bb, so we need to judge both cases.

/ * * *@param {string} s
 * @return {number}* /
var longestPalindrome = function (s) {
  let res = "";
  for (let i = 0; i < s.length; i++) {
    // The longest palindrome string centered around s[I]
    let s1 = isPalindrome(s, i, i);
    // The longest palindrome string centered on s[I] and s[I +1]
    let s2 = isPalindrome(s, i, i + 1);
    res = res.length > s1.length ? res : s1;
    res = res.length > s2.length ? res : s2;
  }
  return res;
};
function isPalindrome(s, l, r) {
  while (l >= 0 && r < s.length && s[l] == s[r]) {
    l--;
    r++;
  }
  return s.substr(l + 1, r - l - 1);
}
Copy the code