当前位置: 代码迷 >> 综合 >> JAVA算法:统计给定字符串中的GFG — 动态规划
  详细解决方案

JAVA算法:统计给定字符串中的GFG — 动态规划

热度:35   发布时间:2024-01-15 19:41:02.0

统计给定字符串中的GFG(Count of ‘GFG’ Subsequences in the given string)

给定一个长度为n的大写字符串。你的任务是统计其中子序列 ‘GFG’ 出现的次数。

举例说明: 

例如给定字符串 : str[] = "GFGFG"

统计输出结果 : 4

GFGFG, GFGFG, GFGFG, GFGFG

例如给定字符串 : str[] = "ABCFGFPG"

统计输出结果 : 1

算法分析

要在给定的字符串中找到“g f g”子序列的数目,请观察每个“f”,如果我们知道“g”前后的数目。那么“f”的“g f g”子序列数等于“f”前后“g”数的乘积。

因此,我们的想法是维护一个数组arr[],其中arr[i]在索引i之前存储“g”的编号,如果字符串的第i个字符是“f”,在索引i之前存储“f”的编号