分割字符串的方法,以便每个分区以不同的字符开头

本文概述

  • C ++
  • Java
  • Python3
  • C#
给定一个字符串s。让?是给定字符串可能的最大分区数, 每个分区均以不同的字符开头。任务是找到可将字符串s拆分成多种方式的方法?分区(非空), 以便每个分区以不同的字符开头。
例子:
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 Subhadeep

Python3
# 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-Ji

C#
// 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

    推荐阅读