本文概述
- C ++
- Java
- Python3
- C#
【分割字符串的方法，使每个分区以不同的字符开始】例子：
Input : s = "abb"
Output : 2
"abb" can be maximum split into 2
partitions {a, bb} with distinct
starting character, so k = 2. And, number of ways to split "abb" into
2 partition with distinct starting
character is 2 that are {a, bb} and
{ab, b}.Input : s = "acbbcc"
Output : 6首先, 我们需要找到k的值。观察到k将等于字符串中不同字符的数量, 因为只有最大数量的分区可以使每个分区具有不同的起始元素。
现在, 找到在每个分区中将字符串分成k个部分的方式的方法数量以不同的字符开始。首先观察一下, 第一个分区将始终固定字符串的第一个字符, 无论它有多长。现在, 我们需要处理除第一个字符以外的所有其他字符。
让我们举一个例子, 假设s =" acbbcc", 我们已经在上面讨论了第一个字符" a"。现在, 要处理" b"和" c", 请观察" b"出现在字符串的两个位置, 而" c"出现在三个位置。如果我们为" b"选择两个位置中的任何位置, 为" c"选择三个位置中的任何一个位置, 则可以在这些位置上对字符串进行分区。请注意, 部分数将等于3(等于s中的不同字符数, 即k)。
所以概括观察, 让我们数一世是字符i在s中出现的次数。所以我们的答案将是计数的乘积一世所有的i都使我出现在字符串中, 并且我不等于字符串的第一个字符。
以下是此方法的实现：
C ++
// CPP Program to find number of way
// to split string such that each partition
// starts with distinct character with
// maximum number of partitions.
#include <
bits/stdc++.h>
using namespace std;
// Returns the number of we can split
// the string
int countWays(string s)
{
int count[26] = { 0 };
// Finding the frequency of each
// character.
for ( char x : s)
count[x - 'a' ]++;
// making frequency of first character
// of string equal to 1.
count展开 - 'a' ] = 1;
// Finding the product of frequency
// of occurrence of each character.
int ans = 1;
for ( int i = 0;
i <
26;
++i)
if (count[i] != 0)
ans *= count[i];
return ans;
}// Driven Program
int main()
{
string s = "acbbcc" ;
cout <
<
countWays(s) <
<
endl;
return 0;
}Java
// Java Program to find number
// of way to split string such
// that each partition starts
// with distinct character with
// maximum number of partitions.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{// Returns the number of we
// can split the string
static int countWays(String s)
{
int count[] = new int [ 26 ];
// Finding the frequency of
// each character.
for ( int i = 0 ;
i <
s.length();
i++)
count展开++;
// making frequency of first
// character of string equal to 1.
count展开 = 1 ;
// Finding the product of frequency
// of occurrence of each character.
int ans = 1 ;
for ( int i = 0 ;
i <
26 ;
++i)
if (count[i] != 0 )
ans *= count[i];
return ans;
}// Driver Code
public static void main(String ags[])
{
String s = "acbbcc" ;
System.out.println(countWays(s));
}
}// This code is contributed
// by SubhadeepPython3
# Python3 Program to find number of way
# to split string such that each partition
# starts with distinct character with
# maximum number of partitions.# Returns the number of we can split
# the string
def countWays(s):
count = [ 0 ] * 26 ;
# Finding the frequency of each
# character.
for x in s:
count[ ord (x) -
ord ( 'a' )] = (count[ ord (x) -
ord ( 'a' )]) + 1 ;
# making frequency of first character
# of string equal to 1.
count[ ord (s[ 0 ]) - ord ( 'a' )] = 1 ;
# Finding the product of frequency
# of occurrence of each character.
ans = 1 ;
for i in range ( 26 ):
if (count[i] ! = 0 ):
ans * = count[i];
return ans;
# Driver Code
if __name__ = = '__main__' :
s = "acbbcc" ;
print (countWays(s));
# This code is contributed by Rajput-JiC#
// C# Program to find number
// of way to split string such
// that each partition starts
// with distinct character with
// maximum number of partitions.using System;
class GFG
{// Returns the number of we
// can split the string
static int countWays( string s)
{
int [] count = new int [26];
// Finding the frequency of
// each character.
for ( int i = 0;
i <
s.Length;
i++)
count展开 - 'a' ]++;
// making frequency of first
// character of string equal to 1.
count展开 - 'a' ] = 1;
// Finding the product of frequency
// of occurrence of each character.
int ans = 1;
for ( int i = 0;
i <
26;
++i)
if (count[i] != 0)
ans *= count[i];
return ans;
}// Driver Code
public static void Main()
{
string s = "acbbcc" ;
Console.WriteLine(countWays(s));
}
}输出如下：
6推荐阅读
- 如何使用OpenCV过滤颜色（代码示例）
- 计算从一个字符串转为另一个字符串的最小编辑次数| DP-5
- Python编程（计算三个数最大值的3中方法）
- 巧妙处理电脑键盘右边的数字键失灵问题
- 注重笔记本保养 经常见故障区分及处理
- 你所不熟悉的显卡各种后缀字母的意义
- 高手详细说明液晶显示器的维护常识
- CPU选购秘籍 简单一招辨别原装与封盒
- 3步骤简单处理开机显示NTLDR is mis的问题