【算法题】2745. 构造最长的新字符串

这篇具有很好参考价值的文章主要介绍了【算法题】2745. 构造最长的新字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

给你三个整数 x ,y 和 z 。

这三个整数表示你有 x 个 “AA” 字符串,y 个 “BB” 字符串,和 z 个 “AB” 字符串。你需要选择这些字符串中的部分字符串(可以全部选择也可以一个都不选择),将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串 “AAA” 或者 “BBB” 。

请你返回新字符串的最大可能长度。

子字符串 是一个字符串中一段连续 非空 的字符序列。

示例 1:

输入:x = 2, y = 5, z = 1
输出:12
解释: 我们可以按顺序连接 “BB” ,“AA” ,“BB” ,“AA” ,“BB” 和 “AB” ,得到新字符串 “BBAABBAABBAB” 。
字符串长度为 12 ,无法得到一个更长的符合题目要求的字符串。
示例 2:

输入:x = 3, y = 2, z = 2
输出:14
解释:我们可以按顺序连接 “AB” ,“AB” ,“AA” ,“BB” ,“AA” ,“BB” 和 “AA” ,得到新字符串 “ABABAABBAABBAA” 。
字符串长度为 14 ,无法得到一个更长的符合题目要求的字符串。

提示:

1 <= x, y, z <= 50

思路:

动态规划文章来源地址https://www.toymoban.com/news/detail-521202.html

java代码:

class Solution {
    int[][][][] memo;

    public int longestString(int x, int y, int z) {
        this.memo = new int[x + 1][y + 1][z + 1][3];
        for (int i = 0; i <= x; ++i) {
            for (int j = 0; j <= y; ++j) {
                for (int k = 0; k <= z; ++k) {
                    Arrays.fill(memo[i][j][k], -1);
                }
            }
        }
        return Math.max(dfs(x, y, z, 0), dfs(x, y, z, 1));
    }

    public int dfs(int x, int y, int z, int k) {
        if (memo[x][y][z][k] != -1) {
            return memo[x][y][z][k];
        }
        int res = 0;
        if (k == 0) {
            if (y > 0) {
                res = dfs(x, y - 1, z, 1) + 2;
            }
        } else {
            if (x > 0) {
                res = dfs(x - 1, y, z, 0) + 2;
            }
            if (z > 0) {
                res = Math.max(res, dfs(x, y, z - 1, 2) + 2);
            }
        }
        memo[x][y][z][k] = res;
        return res;
    }
}

到了这里,关于【算法题】2745. 构造最长的新字符串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 题目:2609.最长平衡子字符串

    ​​ 题目来源:         leetcode题目,网址:2609. 最长平衡子字符串 - 力扣(LeetCode) 解题思路:        按要求进行模拟即可。 解题代码: 总结:         注意,当 1 的数量小于等于 0 的数量,可以组成一个长度为 1 的数量两倍的平衡字符串。         无官方题解。

    2024年02月12日
    浏览(35)
  • 【字符串 简单】LeetCode 14. 最长公共前缀 Java

    我的思路: 给字符串数组按照字符串的长度从长到短排序,因为最长公共前缀最长的话,也只能是字符串数组中最短的那一个字符串 设置一个index变量,表示当前正在检查字符数组中所有字符串的index位置 循环遍历字符串数组n遍,n也就是最长公共前缀的长度 其他思路,方法

    2024年02月15日
    浏览(40)
  • 剑指Offer48.最长不含重复字符的子字符串 C++

    请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1 : 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2 : 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为

    2024年02月12日
    浏览(44)
  • 力扣2182.构造限制重复的字符串

     思路:先记录每个字符的出现次数,构建一个新字符串,从尾取字符,每取一个该字符个数-1,若该字符已经取到有repeatLimit个,则递归取次大的字符,并对应字符个数-1,若没有次大字符了,则直接返回 代码:  

    2024年02月01日
    浏览(47)
  • 2645. 构造有效字符串的最少插入数

    给你一个字符串  word  ,你可以向其中任何位置插入 \\\"a\\\"、\\\"b\\\" 或 \\\"c\\\" 任意次,返回使  word   有效  需要插入的最少字母数。 如果字符串可以由 \\\"abc\\\" 串联多次得到,则认为该字符串  有效  。 示例 1: 示例 2: 示例 3: 提示: 1 = word.length = 50 word  仅由字母 \\\"a\\\"、\\\"b\\\" 和 \\\"c\\\" 组成

    2024年01月20日
    浏览(47)
  • 【每日一题】构造限制重复的字符串

    【贪心】【字符串】【2024-01-13】 2182. 构造限制重复的字符串 思路 解题思想比较简单,利用贪心思想,每次选择当前剩余字符串中字典序最大的字符加到答案字符串末尾,如果答案字符串末尾的字符已经连续出现了 repeatLimit 次,则将字典序次大的字符加到答案字符串,随后

    2024年01月22日
    浏览(44)
  • 【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】

    难度:简单 给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。 在构造过程中,请注意 区分大小写 。比如 \\\"Aa\\\" 不能当做一个回文字符串。 示例 1: 输入:s = “abccccdd” 输出:7 解释: 我们可以构造的最长的回文串是\\\"dccaccd\\\", 它的长度是

    2024年02月01日
    浏览(57)
  • leetcode-2645 构造有效字符串的最小插入数

    题目链接 2645. 构造有效字符串的最少插入数 - 力扣(LeetCode) 解题思路 动态规划 1、定义状态d[i]为将前i个字符(为了方便编码,下标从1开始)拼凑成若干个abc所需要的最小插入数。那么初始状态d[0]=0,最终要求解d[n],其中n为word的长度。 2、转移过程 3、因为每个字符都尽

    2024年02月02日
    浏览(50)
  • go基础10 -字符串的高效构造与转换

    前面提到过,Go原生支持通过+/+=操作符来连接多个字符串以构造一个更长的字符串,并且通过+/+=操作符的字符串连接构造是最自然、开发体验最好的一种。 但Go还提供了其他一些构造字符串的方法,比如: ● 使用fmt.Sprintf; ● 使用strings.Join; ● 使用strings.Builder; ● 使用

    2024年02月09日
    浏览(37)
  • LeetCode-2645. 构造有效字符串的最少插入数

    给你一个字符串 word ,你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次,返回使 word 有效 需要插入的最少字母数。 如果字符串可以由 “abc” 串联多次得到,则认为该字符串 有效 。 示例 1: 输入:word = “b” 输出:2 解释:在 “b” 之前插入 “a” ,在 “b” 之后

    2024年02月02日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包