Data Structure
Networking
RDBMS
Operating System
Java
MS Excel
iOS
HTML
CSS
Android
Python
C Programming
C++
C#
MongoDB
MySQL
Javascript
PHP
- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who
Permutation of a String with Maximum Characters Greater than Adjacent
It is crucial to manipulate strings in various problem-solving scenarios. Discovering a permutation of the given string that optimizes the count of characters larger than their contiguous counterparts presents an enjoyable puzzle, requiring rearranging the string's characters to generate as many pairs as possible of adjacent characters where the left character is lesser than the right.
Methods
There are several methods to solve permutations of a string where maximum number of characters is more than characters immediately adjacent to them.
Method 1 ? Backtracking with Pruning ?
Method 2 ? Dynamic Programming?
Method 3 ? Heap's Algorithm?
Method 4 ? Lexicographic Order with Pruning?
Method 1: Backtracking with Pruning
Use a backtracking algorithm to generate all permutations of the string.
At each step, check if the current permutation has more characters greater than their adjacent characters than the maximum found so far.
If not, prune the branch and backtrack early to avoid unnecessary computations.
Syntax
function backtrack_permutation(string): n = length(string) max_count = [0]
stores the maximum count of characters greater than adjacent characters
result = [None] * n
stores the final permutation
function backtrack(curr_permutation, used_chars): nonlocal max_count if length(cu permutation) == n:
calculate the count of characters greater than adjacent characters
count = 0
for i in range(1, n - 1):
if cu permutation [i - 1] < cu permutation[i] > cu permutation [i + 1]:
count += 1
if count > max count [0]:
max count [0] = count
result [:] = cu permutation
update the result
return
for i in range(n):
if not used_chars[i]:
choose the next character
used_chars[i] = true curr_permutation.append(string[i])
backtrack to the next position
backtrack(curr_permutation, used_chars)
undo the choice
used_chars[i] = false curr_permutation.pop()
start the backtracking process
used_chars = [false] * n
keep track of used characters
curr_permutation = [] backtrack(curr_permutation, used_chars) return result.
Algorithm
Step 1 ? Start max_permutation with a blank string.
The auxiliary function backtracks (current_permutation, remaining_characters) should be defined.
Step 2 ? If the string remaining_characters is empty ?
Set max_permutation to current_permutation if the length of current_permutation is longer than the length of max_permutation.
Return.
Step 3 ? Go through each character in remaining_characters, c, in iterations ?
Add c to current_permutation to create new_permutation.
Skip this iteration if new_permutation's length is greater than 1 and its final character is no longer than its preceding characters.
Take c out of remaining_characters to make a new_remaining.
Call backtracks (new_permutation, new_remaining) iteratively.
Step 4 ? Call the backtrack function, with the input text as remaining_characters and an empty string as current_permutation.
Step 5 ? Provide the output max_permutation.
Example 1
This programme manipulates the input string "abcd" by initially arranging it in an ascending order. Subsequently, every possible permutation is produced using the backtrack function, which reduces the search space considering only characters which are greater than the precedent one, thereby avoiding potential recurring permutations that do not meet the criterions. In addition, the isValidPermutation function evaluates each character with respect to its predecessor, returning false for any case where it is equal or less than the latter.
As a result, this purposeful procedure creates all valid permutations with a maximum number of characters above their neighboring ones. We are free to further customize the given input string, code, and logic to match one's personal requirements.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int maxCount = 0;
bool isValidPermutation(const string& str) {
for (int i = 1; i < str.length(); i++) {
if (str[i] <= str[i - 1]) {
return false;
}
}
return true;
}
void backtrack(string& str, int pos) {
if (pos == str.length()) {
if (isValidPermutation(str)) {
cout << str << endl;
}
return;
}
for (int i = pos; i < str.length(); i++) {
swap(str[pos], str[i]);
if (str[pos] > str[pos - 1]) {
backtrack(str, pos + 1);
}
swap(str[pos], str[i]);
}
}
int main() {
string input = "abcd";
sort(input.begin(), input.end()); // Sort the input string initially
backtrack(input, 1);
return 0;
}
Output
abcd
Method 2: Dynamic Programming
Use dynamic programming to generate permutations of the string incrementally.
Start with an empty prefix and iteratively add characters to it, considering all possible positions.
Maintain a count of the number of characters greater than their adjacent characters in the current prefix.
Prune branches where the count is already lower than the maximum found so far.
Syntax
def find_max_permutation(string): n = len(string) dp = [0] * n dp[0] = 1
Dynamic programming loop
for i in range (1, n):
Check if the current character is greater than its adjacent characters
if string[i] > string[i-1]:
If it is, increase the count by 1
dp[i] = dp[i-1] + 1 else:
If it's not, the count is the same
dp[i] = dp[i-1]
Find the maximum count in the dp array
max_count = max(dp) return max_count
Algorithm
Step 1 ? Create a function called maxPerm(str) that accepts string as input and returns longest string of permutations that satisfies specified criterion.
Step 2 ? Start by initialising array of length n called dp, where n equals the length of the input string str. The largest permutation string that ends at position i is stored in each element dp[i].
Step 3 ? Initialize dp [0] as the first character of the string str.
Step 4 ? Iterate over the characters of str from index 1 to n-1 ?
Initialize an empty string curr to store the current maximum permutation string.
For each character at index i, compare it with the previous character at index i-1.
If str[i] is greater than str[i-1], append str[i] to curr.
Otherwise, append str[i-1] to curr.
Update dp[i] with the maximum value between dp[i-1] and curr.
Step 5 ? After the loop completes, the maximum permutation string will be stored in dp[n-1].
Step 6 ? Return dp[n-1] as the result.
Example 2
In this example, the input string is hardcoded as "abcbdb." The findMaxPermutation function uses dynamic programming to calculate the maximum count of characters greater than their adjacent characters at each index. It then reconstructs the string with the maximum count by backtracking through the table. The resulting maximum permutation is printed in the main function.
#include <iostream>
#include <string>
#include <vector>
std::string findMaxPermutation(const std::string& str) {
int n = str.length();
// make a table to store the maximum count of characters
// larger than their adjacent characters
std::vector<std::vector<int>> dp(n, std::vector<int>(2, 0));
// Initialize the table for the base case
dp[0][0] = 0; // Count when str[0] is not included
dp[0][1] = 1; // Count when str[0] is included
// Calculate the maximum count for each index
for (int i = 1; i < n; i++) {
// When str[i] is not involved, the count is the maximum
// when str[i-1] is included or not
dp[i][0] = std::max(dp[i-1][0], dp[i-1][1]);
// When str[i] is involved, the count is the count when
// str[i-1] is not included plus 1
dp[i][1] = dp[i-1][0] + 1;
}
// The more count will be the largest of the last two values
int maxCount = std::max(dp[n-1][0], dp[n-1][1]);
// Reconstruct the string with the maximum count
std::string maxPerm;
int i = n - 1;
int count = maxCount;
// Start from the end and check which character to include
while (i >= 0) {
if ((dp[i][0] == count - 1 && dp[i][1] == count) || (dp[i][0] == count && dp[i][1] == count)) {
maxPerm = str[i] + maxPerm;
count--;
}
i--;
}
return maxPerm;
}
int main() {
std::string str = "abcbdb";
std::string maxPerm = findMaxPermutation(str);
std::cout << "String: " << str << std::endl;
std::cout << "Max Permutation: " << maxPerm << std::endl;
return 0;
}
Output
String: abcbdb Max Permutation: bbb
Method 3: Heap's Algorithm
Implement Heap's algorithm, which efficiently generates all permutations of a string.
After generating each permutation, count the number of characters greater than their adjacent characters.
Keep track of the maximum count found so far and update it as necessary.
Syntax
function generatePermutations(string):
n = length(string)
characters = array of n elements initialized with string's characters
generatePermutationsHelper(n, characters)
function generatePermutationsHelper(n, characters):
if n = 1:
checkAndPrintPermutation(characters)
else:
for i = 0 to n-1:
generatePermutationsHelper(n-1, characters)
if n is even:
swap characters[i] and characters[n-1]
else:
swap characters [0] and characters[n-1]
Algorithm
Step 1 ? To start an array has been initialized to hold the characters of the input string.
Step 2 ? Moving on a function has been created and named "generatePermutations" with two parameters - a final variable 'size' that determines the size of the array and an array named 'arr' containing string characters.
Step 3 ? If the size is 1 then the current permutation is printed by combining characters in the array until the maximum number of characters exceeds the number of consecutive characters.
Step 4 ? If not the function returns. To iterate over the array from index 0 to 'size - 1' we use a variable called 'i'.
Step 5 ? Within this iteration we further iterate through generatePermutations function with parameter size - 1 and error.
Step 6 ? If size happens to be odd, then we replace element at index 0 in our array with element at index "size - 1".
Step 7 ? Similarly, if size turns out to be even, we replace element at index 'i' in our array with index 'size - 1'.
Step 8 ? Finally, we call "generatePermutations" function using initial Array size as well as Array itself as arguments.
Example 1
The following C++ example creates permutations of a string using Heap's Algorithm and identifies the permutation with the greatest number of characters over its neighbouring characters ?
For illustrational purposes, "abcd" is used as the input string in this example. The variable can be modified to utilise a different input string. If permutation satisfies the requirement of having a maximum number of characters greater than its neighbours, it finds whether isValidPermutation function is valid. The generate Permutations function uses stack approach to keep track of the permutations with most characters so that it can generate every possible permutation of input string. The main function prints the maximum number and the permutation itself as output.
#include <iostream>
#include <algorithm>
using namespace std;
// Function to check if the permutation satisfies the condition
bool isValidPermutation(const string& perm) {
int n = perm.length();
for (int i = 0; i < n - 1; i++) {
if (abs(perm[i] - perm[i + 1]) <= 1)
return false;
}
return true;
}
// Function to swap two characters in a string
void swapChar(char& a, char& b) {
char temp = a;
a = b;
b = temp;
}
// Heap's Algorithm for generating permutations
void generatePermutations(string& str, int n, int& maxCount, string& maxPerm, int idx = 0) {
if (idx == n - 1) {
if (isValidPermutation(str)) {
int count = count_if(str.begin(), str.end(), [](char c) {
return isalpha(c) && c >= 'A' && c <= 'Z';
});
if (count > maxCount) {
maxCount = count;
maxPerm = str;
}
}
return;
}
for (int i = idx; i < n; i++) {
swapChar(str[idx], str[i]);
generatePermutations(str, n, maxCount, maxPerm, idx + 1);
swapChar(str[idx], str[i]);
}
}
int main() {
string str = "abcd";
int n = str.length();
int maxCount = 0;
string maxPerm;
generatePermutations(str, n, maxCount, maxPerm);
if (maxCount == 0) {
cout << "No valid permutation found." << endl;
} else {
cout << "Maximum number of characters greater than adjacent characters: " << maxCount << endl;
cout << "Permutation with the maximum count: " << maxPerm << endl;
}
return 0;
}
Output
No valid permutation found.
Method 4: Lexicographic Order with Pruning
Sort the characters of the string in lexicographic order.
Generate permutations of the sorted string.
At each step, check if the current permutation satisfies the condition of having the maximum number of characters greater than their adjacent characters.
If not, skip the remaining permutations with similar prefixes to avoid unnecessary computations.
Syntax
Function to generate all permutations of a string
function generatePermutations(string):
TODO: Implementation of permutation generation
Function to check if a character is greater than its adjacent character
function isGreaterAdjacent(char1, char2):
TODO: Implementation of the comparison logic
Function to find permutation with maximum number of characters greater than adjacent characters
function findMaxAdjacentPermutation(string):
Generate all permutations of the string
permutations = generatePermutations(string)
Initialize variables
max_permutation = "" max_count = 0
Iterate through each permutation
for permutation in permutations: count = 0
Iterate through each character in the permutation (excluding the last character)
for i from 0 to length(permutation) - 2: char1 = permutation[i] char2 = permutation[i + 1]
Check if the current character is greater than its adjacent character
if isGreaterAdjacent(char1, char2): count = count + 1
Check if the current permutation has a greater count than the previous maximum
if count > max_count: max_permutation = permutation max_count = count
Return the permutation with the maximum count
return max_permutation
Algorithm
Step 1 ? Start with the input string.
Step 2 ? Sort the string in lexicographic order to get the initial permutation.
Step 3 ? Initialize a variable maxCount to 0 to keep track of the maximum count of characters greater than their adjacent characters.
Step 4 ? Initialize a variable maxPermutation to store the permutation with the maximum count.
Step 5 ? While there is a next permutation ?
Initialize a variable count to 0 to keep track of the current count of characters greater than their adjacent characters.
-
For each character in the current permutation ?
Check if the current character is larger than both its previous and next characters (if they exist).
If the condition is fullfilled, increase the count by 1.
-
If the count is greater than maxCount?
Update maxCount to the current count.
Update maxPermutation to the current permutation.
Step 6 ? Return the maxPermutation as the result.
Example 1
For this example, let us consider a fixed string "abcde" for simplicity.
In this example, the countAdjacentGreater function counts the number of adjacent characters in the string that are greater than their preceding characters. The findMaxPermutation function generates all permutations of the input string and checks each permutation to find the one with the maximum count of adjacent characters greater.
The main function initializes the input string "abcde" and the variables to track the maximum count and maximum permutation. It calls the find Max Permutation function to find out the maximum permutation.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int countAdjacentGreater(const string& str) {
int count = 0;
for (int i = 0; i < str.length() - 1; i++) {
if (str[i] < str[i + 1]) {
count++;
}
}
return count;
}
void findMaxPermutation(string& str, int& maxCount, string& maxPerm) {
sort(str.begin(), str.end());
do {
int count = countAdjacentGreater(str);
if (count > maxCount) {
maxCount = count;
maxPerm = str;
}
} while (next_permutation(str.begin(), str.end()));
}
int main() {
string str = "abcde";
int maxCount = 0;
string maxPerm;
findMaxPermutation(str, maxCount, maxPerm);
cout << "String with the maximum number of characters greater than its adjacent characters: " << maxPerm << endl;
cout << "Count of adjacent characters greater in the maximum permutation: " << maxCount << endl;
return 0;
}
Output
String with the maximum number of characters greater than its adjacent characters: abcde Count of adjacent characters greater in the maximum permutation: 4
Conclusion
In conclusion, the problem of finding the permutation of a string with the maximum number of characters greater than their adjacent characters is an interesting challenge in string manipulation. By analyzing the given string and rearranging its characters strategically, it is possible to achieve the desired permutation. This problem highlights the importance of careful examination and creative thinking when working with strings and permutations.
301 Views
