Given a string s. The task is to maximize the removal of characters from s. Any character can be removed if at least one of its adjacent characters is the previous letter in the Latin English alphabet.
Examples:
Input: s = “bacabcab”
Output: 4
Explanation: Following are the removals that maximize the answer.During the first move, the first character can be removed as s1 = b because s2= a.
The string updates to s= acabcab.
During the second move, fifth character can be removed as s5= c because s4= b.
The string updates to s= acabab.
During the third move, sixth character can be removed s6=’b’ because s5= a.
The string updates to s= acaba.
During the fourth move, the only character that can be removed is s4= b, because s3= a (or s5= a).
The string updates to s= acaa. Now it is not possible to remove any character.Therefore, 4 is required answer which is maximum possible.
Input: s = “bcda”
Output: 3
Approach: This problem can be solved by using the Greedy Approach. Follow the steps below to solve the given problem.
- Choose the maximum possible (alphabetically) letter that can be removed and just remove it.
- If maximum letter p is removed that can be used to remove some other letter q in string s.
- It is obvious that s[p]+1=s[q] in such a case.
- If there are no other letters between s[p] and s[q] then s[p] is not the maximum letter.
- Now suppose that if all letters between s[p] and s[q] can be removed. Then first choose s[q] and only after that s[p].
- Consider the last case there is at least one letter s[k] between s[p] and s[q]. Because we cannot remove s[k] then there are only two cases: s[k] – 1 > s[q] or s[k] < s[p] – 1. Then we cannot use s[p] to remove s[q] at all.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <iostream>using namespace std;// Function to find maximum characters that can// be removed with given conditionsint removeMaxCharacters(string s, int n){ // Iterate from the last of english alphabet // so that bigger alphabets are processed first for (int i = 'z'; i > 'a'; i--) { // Iterate in the given string for (int k = 0; k < s.size(); k++) { if (s[k] == i) { if (s[k - 1] == i - 1 || s[k + 1] == i - 1) { s.erase(k, 1); k = -1; } } } } // Return the n-remaining size of s return n - s.size();}// Driver Codeint main(){ string s = "abcde"; // Size of string int N = s.size(); // Function Call cout << removeMaxCharacters(s, N);} |
Java
// Java program for above approachimport java.util.*;public class GFG { // Function to find maximum characters that can // be removed with given conditions static int removeMaxCharacters(String s, int n) { // Iterate from the last of english alphabet // so that bigger alphabets are processed first for (int i = 'z'; i > 'a'; i--) { // Iterate in the given string for (int k = 0; k < s.length(); k++) { if (s.charAt(k) == i) { if (s.charAt(k - 1) == i - 1 || s.charAt(k + 1) == i - 1) { s = s.substring(k); } } } } // Return the n-remaining size of s return n - s.length(); } // Driver Code public static void main(String args[]) { String s = "abcde"; // Size of string int N = s.length(); // Function Call System.out.println(removeMaxCharacters(s, N)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for above approach# Function to find maximum characters that can# be removed with given conditionsdef removeMaxCharacters(s,n): # Iterate from the last of english alphabet # so that bigger alphabets are processed first for i in range(ord('z'),ord('a'),-1): # Iterate in the given string for k in range(len(s)): if (s[k] == chr(i)): if (s[k - 1] == chr(i-1) or s[k + 1] == chr(i-1)): s = s[:k] + s[1+k:] k = -1 # Return the n-remaining size of s return n - len(s)# Driver Codes = "abcde"# Size of stringN = len(s)# Function Callprint(removeMaxCharacters(s, N))# This code is contributed by shinjanpatra |
C#
// C# program for above approachusing System;class GFG { // Function to find maximum characters that can // be removed with given conditions static int removeMaxCharacters(string s, int n) { // Iterate from the last of english alphabet // so that bigger alphabets are processed first for (int i = 'z'; i > 'a'; i--) { // Iterate in the given string for (int k = 0; k < s.Length; k++) { if (s[k] == i) { if (s[k - 1] == i - 1 || s[k + 1] == i - 1) { s = s.Substring(k, 1); } } } } // Return the n-remaining size of s return n - s.Length; } // Driver Code public static void Main() { string s = "abcde"; // Size of string int N = s.Length; // Function Call Console.WriteLine(removeMaxCharacters(s, N)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript program for above approach// Function to find maximum characters that can// be removed with given conditionsfunction removeMaxCharacters(s,n){ // Iterate from the last of english alphabet // so that bigger alphabets are processed first for (let i = 'z'.charCodeAt(0); i > 'a'.charCodeAt(0); i--) { // Iterate in the given string for (let k = 0; k < s.length; k++) { if (s[k] == String.fromCharCode(i)) { if (s[k - 1] == String.fromCharCode(i-1) || s[k + 1] == String.fromCharCode(i-1)) { s = s.split('').splice(k, 1).join(''); k = -1; } } } } // Return the n-remaining size of s return n - s.length;}// Driver Codelet s = "abcde";// Size of stringlet N = s.length;// Function Callconsole.log(removeMaxCharacters(s, N));// This code is contributed by shinjanpatra</script> |
Output
4
Time complexity: O(N2), where N is the length of the string.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
