Java 中的相等计数子串数量

2025年1月6日 | 3 分钟阅读

给定一个整数 count 和一个由小写英文字母组成的字符串 'str'。此问题的目标是找到“等计数子字符串”。当每个不同的字母在子字符串中恰好出现 count 次时，该子字符串就被称为等计数。本质上，任务是识别任何子字符串，其中 count 等于该子字符串中每个唯一字母的频率。接下来，我们必须返回这些子字符串的总数。

示例 1

输入

字符串 str = "aaa"

int count = 3

输出

等计数子字符串的数量是 1

解释

在给定的字符串中，子字符串“aaa”是从索引 0 开始到索引 2 结束的字符串。“aaa”是从索引 0 到索引 2 的子字符串。子字符串中只有“a”字母。

示例 2

输入

字符串 str = "xxxyzyyzz"

int count = 3

输出

等计数子字符串的数量是 3

解释

在给定的字符串中，子字符串“xxx”是从索引 0 开始到索引 2 结束的字符串。子字符串中“x”字母恰好出现三次。“yzyyzz”是位于索引 3 到索引 8 之间的子字符串。子字符串中“y”和“z”字母恰好出现三次。“xxxyzyyzz”是从索引 0 到索引 8 的子字符串。子字符串中“x”、“y”和“z”字母恰好出现三次。

示例 3

输入

字符串 str = "pqrs"

int count = 3

输出

等计数子字符串的数量是 0

解释

在给定的字符串中，每个字母在字符串 'str' 中的出现次数都少于 count 次。因此，返回 0，因为 s 中的任何子字符串都不是等计数子字符串。

方法

实施

文件名: NumberEqualSubstrings.java

import java.io.*;
import java.util.*;
public class NumberEqualSubstrings
{
    // Function to count the number of substrings
    // with the same characters
    public int CountSubstrings(String str, int cnt) 
    {
        int result = 0;
        int N = str.length();
        // iterating through all the possible sub strings
        for (int i = 1; i < 27 && cnt * i <= N; ++i) 
        {
            // finding the length of the sub string
            int m = cnt * i;
            // Temp is used for determining the Character
            // counts in the current substring
            // that are stored in an array.
            int[] temp = new int[26];
            int j = 0;
            // Use a loop to iterate through the string's characters
            for (int k = 0; k < N; ++k) 
            {
                int a = str.charAt(i) - 'a';
                ++temp[a];
                if (temp[a] == cnt) 
                {
                    ++j;
                }
                if (temp[a] == cnt + 1) 
                {
                    --j;
                }
                // The current substring's starting index
                // should be determined.
                int y = k - m;
                // finding if the sub string length is valid or not 
                if (y >= 0) 
                {
                    int b = str.charAt(j) - 'a';
                    --temp[b];
                    if (temp[b] == cnt) 
                    {
                        ++j;
                    }
                    if (temp[b] == cnt - 1) 
                    {
                        --j;
                    }
                }
                // Verify that the substring's beginning 
                // and ending indexes are equal.
                if (i == j) 
                {
                    ++result;
                }
            }
        }
        return result;
    }
    public static void main(String[] args) throws IOException 
    {
        NumberEqualSubstrings obj = new NumberEqualSubstrings();
        String str = "aaa";
        int cnt = 3 ;
        int result = obj.CountSubstrings(str, cnt);
        System.out.println("The number of equal count of sub strings is : " + result);
    }
}

输出

The number of equal counts of sub strings is : 1

复杂度分析

上述代码的时间复杂度为 O(N)，空间复杂度为 O(1)。

下一个主题检查给定的字符串是否是偶数/奇数回文数或不是Java

Java 中的相等计数子串数量

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的相等计数子串数量

实施

相关帖子

Java SAML

Java Pass by Value

Java 静态字段初始化

Java 中用于先序遍历的 Morris 遍历

Java 中的平衡素数

Java 中 this 关键字的用法

Java 中集合位计数最多为 K 的最大整数

Java 中字符流和字节流的区别

Java 中 Fork/Join 框架和 ExecutorService 的区别

Java Operator Precedence

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器