给定一个字符串和一个正整数d，重新排列给定字符串的字符，使相同的字符彼此之间的距离至少为d。
null
请注意，可能有许多可能的重排，输出应该是可能的重排之一。如果不可能做出这样的安排，也应报告。
预期的时间复杂度为O（n），其中n是输入字符串的长度。
例如：
Input: "aaaabbbcc", d = 2Output: "ababacabc" Input: "aacbbc", d = 3Output: "abcabc" Input: "geeksforgeeks", d = 3Output: egkesfegkeorsInput: "aaa", d = 2Output: Cannot be rearranged
我们已经讨论过了 如何将相同的字符精确地放置在d距离之外 .这是一个扩展版本，相同的字符应移动至少d距离。
其想法是使用额外的空间来存储所有字符的频率，并保持一个数组，以便在正确的距离插入值。以下是完整的算法——
- 假设给定字符串为str，字符串大小为n，字母表大小为256（一个常数）。
- 我们扫描输入字符串str并将所有字符的频率存储在数组freq中。
- 我们创建一个数组dist[]，用于以正确的距离插入值。dist[j]将存储当前位置和下一个位置之间的最小距离，我们可以使用字符“j”。 如果dist[j]<=0，则可以在当前位置插入字符“j”。
- 循环n次
- 搜索下一个符合条件的字符，最大频率和距离[j]<=0。
- 如果我们找到了这样的字符，我们将该字符放在输出数组中的下一个可用位置，降低其频率，并将其距离重置为d。如果我们没有找到任何字符，字符串将无法重新排列，我们将返回false。
- 当我们在输出字符串中向前移动时，我们将dist[]中所有字符的距离减少1。
下面是上述算法的实现。
C++
// C++ program to rearrange a string so that all same // characters become atleast d distance away #include <bits/stdc++.h> #define MAX_CHAR 256 using namespace std; // The function returns next eligible character // with maximum frequency (Greedy!!) and // zero or negative distance int nextChar( int freq[], int dist[]) { int max = INT_MIN; for ( int i = 0; i < MAX_CHAR; i++) if (dist[i] <= 0 && freq[i] > 0 && (max == INT_MIN || freq[i] > freq[max])) max = i; return max; } // The main function that rearranges input string 'str' // such that two same characters become atleast d // distance away int rearrange( char str[], char out[], int d) { // Find length of input string int n = strlen (str); // Create an array to store all characters and their // frequencies in str[] int freq[MAX_CHAR] = { 0 }; // Traverse the input string and store frequencies // of all characters in freq[] array. for ( int i = 0; i < n; i++) freq[str[i]]++; // Create an array for inserting the values at // correct distance dist[j] stores the least distance // between current position and the next position we // can use character 'j' int dist[MAX_CHAR] = { 0 }; for ( int i = 0; i < n; i++) { // find next eligible character int j = nextChar(freq, dist); // return 0 if string cannot be rearranged if (j == INT_MIN) return 0; // Put character j at next position out[i] = j; // decrease its frequency freq[j]--; // set distance as d dist[j] = d; // decrease distance of all characters by 1 for ( int i = 0; i < MAX_CHAR; i++) dist[i]--; } // null terminate output string out[n] = ' ' ; // return success return 1; } // Driver code int main() { char str[] = "aaaabbbcc" ; int n = strlen (str); // To store output char out[n]; if (rearrange(str, out, 2)) cout << out; else cout << "Cannot be rearranged" ; return 0; } |
JAVA
// Java program to rearrange a string so that all same // characters become atleast d distance away import java.util.*; class GFG { static int MAX_CHAR = 256 ; // The function returns next eligible character // with maximum frequency (Greedy!!) and // zero or negative distance static int nextChar( int freq[], int dist[]) { int max = Integer.MIN_VALUE; for ( int i = 0 ; i < MAX_CHAR; i++) if (dist[i] <= 0 && freq[i] > 0 && (max == Integer.MIN_VALUE || freq[i] > freq[max])) max = i; return max; } // The main function that rearranges input string 'str' // such that two same characters become atleast d // distance away static int rearrange( char str[], char out[], int d) { // Find length of input string int n = str.length; // Create an array to store all characters and their // frequencies in str[] int []freq = new int [MAX_CHAR]; // Traverse the input string and store frequencies // of all characters in freq[] array. for ( int i = 0 ; i < n; i++) freq[str[i]]++; // Create an array for inserting the values at // correct distance dist[j] stores the least distance // between current position and the next position we // can use character 'j' int []dist = new int [MAX_CHAR]; for ( int i = 0 ; i < n; i++) { // find next eligible character int j = nextChar(freq, dist); // return 0 if string cannot be rearranged if (j == Integer.MIN_VALUE) return 0 ; // Put character j at next position out[i] = ( char ) j; // decrease its frequency freq[j]--; // set distance as d dist[j] = d; // decrease distance of all characters by 1 for ( int k = 0 ; k < MAX_CHAR; k++) dist[k]--; } // null terminate output string Arrays.copyOfRange(out, 0 , n); // out[n] = ' '; // return success return 1 ; } // Driver code public static void main(String[] args) { char str[] = "aaaabbbcc" .toCharArray(); int n = str.length; // To store output char []out = new char [n]; if (rearrange(str, out, 2 )== 1 ) System.out.println(String.valueOf(out)); else System.out.println( "Cannot be rearranged" ); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to rearrange a string so that all # same characters become at least d distance away MAX_CHAR = 256 # The function returns next eligible character # with maximum frequency (Greedy!!) # and zero or negative distance def nextChar(freq, dist): Max = float ( '-inf' ) for i in range ( 0 , MAX_CHAR): if (dist[i] < = 0 and freq[i] > 0 and ( Max = = float ( '-inf' ) or freq[i] > freq[ Max ])): Max = i return Max # The main function that rearranges input # string 'str' such that two same characters # become atleast d distance away def rearrange(string, out, d): # Find length of input string n = len (string) # Create an array to store all characters # and their frequencies in str[] freq = [ 0 ] * MAX_CHAR # Traverse the input string and store frequencies # of all characters in freq[] array. for i in range ( 0 , n): freq[ ord (string[i])] + = 1 # Create an array for inserting the values at # correct distance dist[j] stores the least # distance between current position and the # we next position can use character 'j' dist = [ 0 ] * MAX_CHAR for i in range ( 0 , n): # find next eligible character j = nextChar(freq, dist) # return 0 if string cannot be rearranged if j = = float ( '-inf' ): return 0 # Put character j at next position out[i] = chr (j) # decrease its frequency freq[j] - = 1 # set distance as d dist[j] = d # decrease distance of all characters by 1 for i in range ( 0 , MAX_CHAR): dist[i] - = 1 # return success return 1 # Driver code if __name__ = = "__main__" : string = "aaaabbbcc" n = len (string) # To store output out = [ None ] * n if rearrange(string, out, 2 ): print (''.join(out)) else : print ( "Cannot be rearranged" ) # This code is contributed by Rituraj Jain |
C#
// C# program to rearrange a string so that all same // characters become atleast d distance away using System; class GFG { static int MAX_CHAR = 256; // The function returns next eligible character // with maximum frequency (Greedy!!) and // zero or negative distance static int nextChar( int []freq, int []dist) { int max = int .MinValue; for ( int i = 0; i < MAX_CHAR; i++) if (dist[i] <= 0 && freq[i] > 0 && (max == int .MinValue || freq[i] > freq[max])) max = i; return max; } // The main function that rearranges input string 'str' // such that two same characters become atleast d // distance away static int rearrange( char []str, char []ouT, int d) { // Find length of input string int n = str.Length; // Create an array to store all characters and their // frequencies in str[] int []freq = new int [MAX_CHAR]; // Traverse the input string and store frequencies // of all characters in freq[] array. for ( int i = 0; i < n; i++) freq[str[i]]++; // Create an array for inserting the values at // correct distance dist[j] stores the least distance // between current position and the next position we // can use character 'j' int []dist = new int [MAX_CHAR]; for ( int i = 0; i < n; i++) { // find next eligible character int j = nextChar(freq, dist); // return 0 if string cannot be rearranged if (j == int .MinValue) return 0; // Put character j at next position ouT[i] = ( char ) j; // decrease its frequency freq[j]--; // set distance as d dist[j] = d; // decrease distance of all characters by 1 for ( int k = 0; k < MAX_CHAR; k++) dist[k]--; } // null terminate output string Array.Copy(ouT,ouT, n); // out[n] = ' '; // return success return 1; } // Driver code public static void Main(String[] args) { char []str = "aaaabbbcc" .ToCharArray(); int n = str.Length; // To store output char []ouT = new char [n]; if (rearrange(str, ouT, 2)==1) Console.WriteLine(String.Join( "" ,ouT)); else Console.WriteLine( "Cannot be rearranged" ); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to rearrange a // string so that all same characters // become atleast d distance away let MAX_CHAR = 256; // The function returns next eligible // character with maximum frequency // (Greedy!!) and zero or negative distance function nextChar(freq, dist) { let max = Number.MIN_VALUE; for (let i = 0; i < MAX_CHAR; i++) if (dist[i] <= 0 && freq[i] > 0 && (max == Number.MIN_VALUE || freq[i] > freq[max])) max = i; return max; } // The main function that rearranges input // string 'str' such that two same characters // become atleast d distance away function rearrange(str, out, d) { // Find length of input string let n = str.length; // Create an array to store all characters // and their frequencies in str[] let freq = new Array(MAX_CHAR); for (let i = 0; i < freq.length; i++) { freq[i] = 0; } // Traverse the input string and store // frequencies of all characters in // freq[] array. for (let i = 0; i < n; i++) freq[str[i].charCodeAt(0)]++; // Create an array for inserting the // values at correct distance dist[j] // stores the least distance between // current position and the next position // we can use character 'j' let dist = new Array(MAX_CHAR); for (let i = 0; i < dist.length; i++) { dist[i] = 0; } for (let i = 0; i < n; i++) { // Find next eligible character let j = nextChar(freq, dist); // return 0 if string cannot // be rearranged if (j == Number.MIN_VALUE) return 0; // Put character j at next position out[i] = String.fromCharCode (j); // Decrease its frequency freq[j]--; // Set distance as d dist[j] = d; // Decrease distance of all // characters by 1 for (let k = 0; k < MAX_CHAR; k++) dist[k]--; } // Null terminate output string // Arrays.copyOfRange(out, 0, n); // out[n] = ' '; // Return success return 1; } // Driver code let str= "aaaabbbcc" .split( "" ); let n = str.length; // To store output let out = new Array(n); if (rearrange(str, out, 2) == 1) document.write(out.join( "" )); else document.write( "Cannot be rearranged" ); // This code is contributed by rag2127 </script> |
输出：
ababacabc
本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
