This is the 8th day of my participation in the August Text Challenge.More challenges in August

5193. Delete characters to make strings better

A string is a good string if it does not have three consecutive identical characters.

Given a string s, please remove the minimum number of characters from s to make it a good string.

Please return the deleted string. The question data ensures that the answer is always unique.

 

Example 1:

Input: s = “leeetCode” Output: “leetCode” Explanation: Remove an ‘e’ from the first group ‘e’ to get “leetcode”. No three consecutive characters are the same, so return “leetcode”. Example 2:

Input: s = “aaabaaaa” Output: “aabaa” Explanation: Delete an ‘A’ from the first group ‘a’ to get “aabaaaa”. Delete two ‘as’ from the second ‘a’ to get “aabaa”. No three consecutive characters are the same, so return “aabaa”. Example 3:

Input: s = “aab” Output: “aab” Explanation: There are no three identical characters in a row, so “aab” is returned.

Their thinking

When three consecutive characters are encountered, the resulting string is guaranteed to be a good string by not adding the final string

code

class Solution {
    public String makeFancyString(String s) {

        char pre=s.charAt(0);
        int cnt=1,res=0;
        StringBuilder stringBuilder=new StringBuilder();
                stringBuilder.append(pre);
        for (int i=1; i<s.length(); i++) {if(s.charAt(i)==pre)
            {
                if (++cnt<=2) { stringBuilder.append(s.charAt(i)); }}else{
                cnt=1; pre=s.charAt(i); stringBuilder.append(pre); }}returnstringBuilder.toString(); }}Copy the code

1137. The NTH Tebonacci number

Tn of The Tebonacci sequence is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn+ Tn+1 + Tn+2 under n >= 0

Given the integer n, please return the value of the NTH Tebonacci number Tn.

  • Example 1:

Input: n = 4 Output: 4 Description: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

  • Example 2:

Input: n = 25 Output: 1389537

Tip:

0 <= n <= 37

Their thinking

We use recursion, because the recursion formula they gave us, Tn+3 is equal to Tn+ Tn+1 + Tn+2, so we can just recurse directly

code

class Solution {
    public int tribonacci(int n) {

         
        int[] dp = new int[n + 1];       
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        if(n==3) return 2;
        dp[0] =0;
        dp[1] =1;
        dp[2] =1;
        dp[3] =2;
        for (int i=4; i<=n; i++) dp[i]=dp[i-1] *2-dp[i-4];
        returndp[n]; }}Copy the code