给定一个由三个字母“a”、“b”和“c”组合而成的字符串，找出可通过重复应用以下操作获得的最小字符串的长度：
null
取任意两个相邻的、不同的字符，并用第三个替换它们。
例如：
Input : cabOutput : 2We can select any two adjacent letters, say 'ca' and transform it into 'b', this leaves us with string 'bb' of length two. Input : bcabOutput : 1Selecting 'bc' and transforming it to 'a' leaves us with 'aab'. We can then select'ab' and transform it to 'c', giving 'ac'. This can further be transformed into 'b',which is of length one.
一种简单的方法是找到所有可能的替换，然后递归，直到找到最小字符串。这需要大量的时间。
引理 ：字母顺序不影响最小字符串的长度或值。
归纳法证明 基本情况 ：以字符串’ab’和’ba’为例，它们都减少为’c’
归纳假说 ：假设每个字符串中每个字母的出现次数相同，则长度<=k的所有字符串将减少为相同的字符串。
感应步 ：取两个长度为k+1的字符串，每个字母的出现次数相同。找到一对相邻的字母
在两个字符串中。这里出现了两种情况：
- 我们设法找到了这样一对字母。然后我们可以用第三个字母替换这些字母，从而得到两个长度为k的字符串，每个字母的出现次数相同，通过归纳假设，这两个字符串减少为同一个字符串。i、 e.我们有’abcacb’和’accba’，并在两个字符串中减少’ac’，因此我们得到’abcbb’和’bcbba’。
- 我们找不到这样一对。当字符串中的所有字母都相同时，就会出现这种情况。在这种情况下，两个字符串本身是相同的，即“ccccccc”和“ccccccc”。
因此，通过归纳，我们已经证明了这个引理。
动态规划方法 我们现在可以用动态规划来设计一个函数来解决这个问题。
C++
// C++ program to find smallest possible length // of a string of only three characters #include<bits/stdc++.h> using namespace std; // Program to find length of reduced string // in a string made of three characters. #define MAX_LEN 110 // To store results of subproblems int DP[MAX_LEN][MAX_LEN][MAX_LEN]; // A memoized function find result recursively. // a, b and c are counts of 'a's, 'b's and // 'c's in str int length( int a, int b, int c) { // If this subproblem is already evaluated if (DP[a][b] != -1) return DP[a][b]; // If there is only one type of character if (a == 0 && b == 0) return (DP[a][b] = c); if (a == 0 && c == 0) return (DP[a][b] = b); if (b == 0 && c == 0) return (DP[a][b] = a); // If only two types of characters are present if (a == 0) return (DP[a][b] = length(a + 1, b - 1, c - 1)); if (b == 0) return (DP[a][b] = length(a - 1, b + 1, c - 1)); if (c == 0) return (DP[a][b] = length(a - 1, b - 1, c + 1)); // If all types of characters are present. // Try combining all pairs. return (DP[a][b] = min(length(a - 1, b - 1, c + 1), min(length(a - 1, b + 1, c - 1), length(a + 1, b - 1, c - 1)))); } // Returns smallest possible length with given // operation allowed. int stringReduction(string str) { int n = str.length(); // Counting occurrences of three different // characters 'a', 'b' and 'c' in str int count[3] = {0}; for ( int i=0; i<n; ++i) count[str[i]- 'a' ]++; // Initialize DP[][] entries as -1 for ( int i = 0; i <= count[0]; ++i) for ( int j = 0; j < count[1]; ++j) for ( int k = 0; k < count[2]; ++k) DP[i][j][k] = -1; return length(count[0], count[1], count[2]); } // Driver code int main() { string str = "abcbbaacb" ; cout << stringReduction(str); return 0; } |
JAVA
// Java program to find smallest possible length // of a string of only three characters import java.io.*; class GFG { static int MAX_LEN = 110 ; // Program to find length of reduced string // in a string made of three characters. static int [][][] DP = new int [MAX_LEN][MAX_LEN][MAX_LEN]; // A memoized function find result recursively. // a, b and c are counts of 'a's, 'b's and // 'c's in str static int length( int a, int b, int c) { // If this subproblem is already // evaluated if (a < 0 || b < 0 || c < 0 ) // If this subproblem is already evaluated if (DP[a][b] != - 1 ) return DP[a][b]; // If there is only one type of character if (a == 0 && b == 0 ) return (DP[a][b] = c); if (a == 0 && c == 0 ) return (DP[a][b] = b); if (b == 0 && c == 0 ) return (DP[a][b] = a); // If only two types of characters are present if (a == 0 ) return (DP[a][b] = length(a + 1 , b - 1 , c - 1 )); if (b == 0 ) return (DP[a][b] = length(a - 1 , b + 1 , c - 1 )); if (c == 0 ) return (DP[a][b] = length(a - 1 , b - 1 , c + 1 )); // If all types of characters are present. // Try combining all pairs. DP[a][b] = Math.min(length(a - 1 , b - 1 , c + 1 ), Math.min(length(a - 1 , b + 1 , c - 1 ), length(a + 1 , b - 1 , c - 1 ))); return DP[a][b]; } // Returns smallest possible length with given // operation allowed. static int stringReduction(String str) { int n = str.length(); // Counting occurrences of three different // characters 'a', 'b' and 'c' in str int [] count = new int [ 3 ]; for ( int i = 0 ; i < n; ++i) count[str.charAt(i) - 'a' ]++; // Initialize DP[][] entries as -1 for ( int i = 0 ; i <= count[ 0 ]; ++i) for ( int j = 0 ; j < count[ 1 ]; ++j) for ( int k = 0 ; k < count[ 2 ]; ++k) DP[i][j][k] = - 1 ; return length(count[ 0 ], count[ 1 ], count[ 2 ]); } // Driver code public static void main (String[] args) { String str = "abcbbaacb" ; System.out.println(stringReduction(str)); } } // This code is contributed by rag2127 |
Python3
# Python3 program to find smallest possible # length of a string of only three characters # A memoized function find result recursively. # a, b and c are counts of 'a's, 'b's and # 'c's in str def length(a, b, c): global DP #print(a, b, c) # If this subproblem is already # evaluated if a < 0 or b < 0 or c < 0 : return 0 if (DP[a][b] ! = - 1 ): return DP[a][b] # If there is only one type # of character if (a = = 0 and b = = 0 ): DP[a][b] = c return c if (a = = 0 and c = = 0 ): DP[a][b] = b return b if (b = = 0 and c = = 0 ): DP[a][b] = a return a # If only two types of characters # are present if (a = = 0 ): DP[a][b] = length(a + 1 , b - 1 , c - 1 ) return DP[a][b] if (b = = 0 ): DP[a][b] = length(a - 1 , b + 1 , c - 1 ) return DP[a][b] if (c = = 0 ): DP[a][b] = length(a - 1 , b - 1 , c + 1 ) return DP[a][b] # If all types of characters are present. # Try combining all pairs. x = length(a - 1 , b - 1 , c + 1 ) y = length(a - 1 , b + 1 , c - 1 ) z = length(a + 1 , b - 1 , c - 1 ) DP[a][b] = min ([x, y, z]) return DP[a][b] # Returns smallest possible length with # given operation allowed. def stringReduction( str ): n = len ( str ) # Counting occurrences of three different # characters 'a', 'b' and 'c' in str count = [ 0 ] * 3 for i in range (n): count[ ord ( str [i]) - ord ( 'a' )] + = 1 return length(count[ 0 ], count[ 1 ], count[ 2 ]) # Driver code if __name__ = = '__main__' : DP = [[[ - 1 for i in range ( 110 )] for i in range ( 110 )] for i in range ( 110 )] str = "abcbbaacb" print (stringReduction( str )) # This code is contributed by mohit kumar 29 |
C#
// C# program to find smallest possible length // of a string of only three characters using System; public class GFG { static int MAX_LEN = 110; // Program to find length of reduced string // in a string made of three characters. static int [,,] DP = new int [MAX_LEN, MAX_LEN, MAX_LEN]; // A memoized function find result recursively. // a, b and c are counts of 'a's, 'b's and // 'c's in str static int length( int a, int b, int c) { // If this subproblem is already // evaluated if (a < 0 || b < 0 || c < 0) // If this subproblem is already evaluated if (DP[a, b, c] != -1) return DP[a, b, c]; // If there is only one type of character if (a == 0 && b == 0) return (DP[a, b, c] = c); if (a == 0 && c == 0) return (DP[a, b, c] = b); if (b == 0 && c == 0) return (DP[a, b, c] = a); // If only two types of characters are present if (a == 0) return (DP[a, b, c] = length(a + 1, b - 1, c - 1)); if (b == 0) return (DP[a, b, c] = length(a - 1, b + 1, c - 1)); if (c == 0) return (DP[a, b, c] = length(a - 1, b - 1, c + 1)); // If all types of characters are present. // Try combining all pairs. DP[a, b, c] = Math.Min(length(a - 1, b - 1, c + 1), Math.Min(length(a - 1, b + 1, c - 1), length(a + 1, b - 1, c - 1))); return DP[a, b, c]; } // Returns smallest possible length with given // operation allowed. static int stringReduction( string str) { int n = str.Length; // Counting occurrences of three different // characters 'a', 'b' and 'c' in str int [] count = new int [3]; for ( int i = 0; i < n; ++i) count[str[i] - 'a' ]++; // Initialize DP[][] entries as -1 for ( int i = 0; i <= count[0]; ++i) for ( int j = 0; j < count[1]; ++j) for ( int k = 0; k < count[2]; ++k) DP[i, j, k] = -1; return length(count[0], count[1], count[2]); } // Driver code static public void Main () { string str = "abcbbaacb" ; Console.WriteLine(stringReduction(str)); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program to find smallest possible length // of a string of only three characters let MAX_LEN = 110; // Program to find length of reduced string // in a string made of three characters. let DP = new Array(MAX_LEN); for (let i = 0; i < DP.length; i++) { DP[i] = new Array(MAX_LEN); for (let j = 0; j < DP[i].length; j++) { DP[i][j] = new Array(MAX_LEN); for (let k = 0; k < MAX_LEN; k++) { DP[i][j][k] = 0; } } } // A memoized function find result recursively. // a, b and c are counts of 'a's, 'b's and // 'c's in str function length(a, b, c) { // If this subproblem is already // evaluated if (a < 0 || b < 0 || c < 0) // If this subproblem is already evaluated if (DP[a][b] != -1) return DP[a][b]; // If there is only one type of character if (a == 0 && b == 0) return (DP[a][b] = c); if (a == 0 && c == 0) return (DP[a][b] = b); if (b == 0 && c == 0) return (DP[a][b] = a); // If only two types of characters are present if (a == 0) return (DP[a][b] = length(a + 1, b - 1, c - 1)); if (b == 0) return (DP[a][b] = length(a - 1, b + 1, c - 1)); if (c == 0) return (DP[a][b] = length(a - 1, b - 1, c + 1)); // If all types of characters are present. // Try combining all pairs. DP[a][b] = Math.min(length(a - 1, b - 1, c + 1), Math.min(length(a - 1, b + 1, c - 1), length(a + 1, b - 1, c - 1))); return DP[a][b]; } // Returns smallest possible length with given // operation allowed. function stringReduction(str) { let n = str.length; // Counting occurrences of three different // characters 'a', 'b' and 'c' in str let count = new Array(3); for (let i = 0; i < 3; i++) { count[i] = 0; } for (let i = 0; i < n; ++i) count[str[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; // Initialize DP[][] entries as -1 for (let i = 0; i <= count[0]; ++i) for (let j = 0; j < count[1]; ++j) for (let k = 0; k < count[2]; ++k) DP[i][j][k] = -1; return length(count[0], count[1], count[2]); } // Driver code let str = "abcbbaacb" ; document.write(stringReduction(str)); // This code is contributed by unknown2108 </script> |
输出：
1
在最坏的情况下，每个字母出现在整个字符串的三分之一中。这导致辅助空间=O（N 3. )时间复杂度=O（N 3. )
Space Complexity = O(N^3)Time Complexity = O(N^3)
数学方法 我们可以通过三个主要原则做得更好：
- 如果字符串不能进一步缩小，那么字符串中的所有字母都是相同的。
- 最小字符串的长度小于等于2或等于原始字符串的长度，或者2
- 如果字符串的每个字母出现奇数次，经过一个缩减步骤后，它们都应出现偶数次。反之亦然，也就是说，如果字符串的每个字母出现偶数次，那么在一个缩减步骤后，它们应该出现奇数次。
这些可以证明如下：
- 如果存在任何两个不同的字母，我们可以选择它们并进一步缩短字符串长度。
- 矛盾证明： 假设我们有一个长度小于原始字符串的缩减字符串。例如“bbbbb”。那么这个字符串一定是由类似“acbbbb”、“bbacbbbb”或任何其他类似组合的字符串产生的。在这种情况下，我们可以选择“bc”而不是“ac”，并进一步减少。
- 通过上面的递归步骤，我们将一个字母增加一个，将另外两个字母减少一个。所以如果我们有一个组合as（奇数，奇数，奇数），那么它会变成（奇数+1，奇数-1，奇数-1）或（偶数，偶数，偶数）。反面也以类似的方式显示。
现在我们可以结合上述原则。 如果字符串由相同的重复字母组成，它的最小缩减字符串就是它本身，长度就是字符串的长度。 现在，其他可能的选择是减少字符串长度为一个或两个字符。现在，如果所有字符出现偶数次或奇数次，唯一可能的答案是2，因为（0，2，0）是（偶数，偶数，偶数），而（0，1，0）是（偶数，奇数，偶数），所以只有2保持这种均匀性。 在任何其他条件下，答案为1。
C++
// C++ program to find smallest possible length // of a string of only three characters #include<bits/stdc++.h> using namespace std; // Returns smallest possible length with given // operation allowed. int stringReduction(string str) { int n = str.length(); // Counint occurrences of three different // characters 'a', 'b' and 'c' in str int count[3] = {0}; for ( int i=0; i<n; ++i) count[str[i]- 'a' ]++; // If all characters are same. if (count[0] == n || count[1] == n || count[2] == n) return n; // If all characters are present even number // of times or all are present odd number of // times. if ((count[0] % 2) == (count[1] % 2) && (count[1] % 2) == (count[2] % 2)) return 2; // Answer is 1 for all other cases. return 1; } // Driver code int main() { string str = "abcbbaacb" ; cout << stringReduction(str); return 0; } |
JAVA
// Java program to find smallest possible length // of a string of only three characters public class GFG { // Returns smallest possible length with given // operation allowed. static int stringReduction(String str) { int n = str.length(); // Counint occurrences of three different // characters 'a', 'b' and 'c' in str int count[] = new int [ 3 ]; for ( int i = 0 ; i < n; ++i) { count[str.charAt(i) - 'a' ]++; } // If all characters are same. if (count[ 0 ] == n || count[ 1 ] == n || count[ 2 ] == n) { return n; } // If all characters are present even number // of times or all are present odd number of // times. if ((count[ 0 ] % 2 ) == (count[ 1 ] % 2 ) && (count[ 1 ] % 2 ) == (count[ 2 ] % 2 )) { return 2 ; } // Answer is 1 for all other cases. return 1 ; } // Driver code public static void main(String[] args) { String str = "abcbbaacb" ; System.out.println(stringReduction(str)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find smallest possible # length of a string of only three characters # Returns smallest possible length # with given operation allowed. def stringReduction( str ): n = len ( str ) # Counint occurrences of three different # characters 'a', 'b' and 'c' in str count = [ 0 ] * 3 for i in range (n): count[ ord ( str [i]) - ord ( 'a' )] + = 1 # If all characters are same. if (count[ 0 ] = = n or count[ 1 ] = = n or count[ 2 ] = = n): return n # If all characters are present even number # of times or all are present odd number of # times. if ((count[ 0 ] % 2 ) = = (count[ 1 ] % 2 ) and (count[ 1 ] % 2 ) = = (count[ 2 ] % 2 )): return 2 # Answer is 1 for all other cases. return 1 # Driver code if __name__ = = "__main__" : str = "abcbbaacb" print (stringReduction( str )) # This code is contributed by ita_c |
C#
// C# program to find smallest possible length // of a string of only three characters using System; public class GFG { // Returns smallest possible length with given // operation allowed. static int stringReduction(String str) { int n = str.Length; // Counint occurrences of three different // characters 'a', 'b' and 'c' in str int []count = new int [3]; for ( int i = 0; i < n; ++i) { count[str[i] - 'a' ]++; } // If all characters are same. if (count[0] == n || count[1] == n || count[2] == n) { return n; } // If all characters are present even number // of times or all are present odd number of // times. if ((count[0] % 2) == (count[1] % 2) && (count[1] % 2) == (count[2] % 2)) { return 2; } // Answer is 1 for all other cases. return 1; } // Driver code public static void Main() { String str = "abcbbaacb" ; Console.WriteLine(stringReduction(str)); } } // This code is contributed by 29AjayKumar |
PHP
<?php // PHP program to find smallest possible length // of a string of only three characters // Returns smallest possible length with // given operation allowed. function stringReduction( $str ) { $n = strlen ( $str ); // Counint occurrences of three different // characters 'a', 'b' and 'c' in str $count = array_fill (0, 3, 0); for ( $i = 0; $i < $n ; ++ $i ) $count [ord( $str [ $i ]) - ord( 'a' )]++; // If all characters are same. if ( $count [0] == $n || $count [1] == $n || $count [2] == $n ) return $n ; // If all characters are present even number // of times or all are present odd number of // times. if (( $count [0] % 2) == ( $count [1] % 2) && ( $count [1] % 2) == ( $count [2] % 2)) return 2; // Answer is 1 for all other cases. return 1; } // Driver code $str = "abcbbaacb" ; print (stringReduction( $str )); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to find smallest // possible length of a string of only // three characters // Returns smallest possible length // with given operation allowed. function stringReduction(str) { var n = str.length; // Counvar occurrences of three different // characters 'a', 'b' and 'c' in str var count = Array.from({length: 3}, (_, i) => 0); for ( var i = 0; i < n; ++i) { count[str.charAt(i).charCodeAt(0) - 'a' .charCodeAt(0)]++; } // If all characters are same. if (count[0] == n || count[1] == n || count[2] == n) { return n; } // If all characters are present even number // of times or all are present odd number of // times. if ((count[0] % 2) == (count[1] % 2) && (count[1] % 2) == (count[2] % 2)) { return 2; } // Answer is 1 for all other cases. return 1; } // Driver code var str = "abcbbaacb" ; document.write(stringReduction(str)); // This code is contributed by Princi Singh </script> |
输出：
1
时间复杂性： O（n） 辅助空间： O（1）
本文由 阿迪蒂亚·卡玛斯 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
