Given a string W, change the string in such a way that it does not contain any of the “forbidden” strings S1 to Sn as one of its substrings. The rules that govern this change are as follows:
- Case of the characters does not matter i.e “XyZ” is the same as “xYZ”.
- Change all the characters that are covered by the substrings in the original string W such that a particular letter lt occurs a maximum number of times in the changed string and the changed string is lexicographically the smallest string that can be obtained from all possible combinations.
- Characters that are not within the forbidden substrings are not allowed to change.
- The case of the changed character must be the same as the case of the original character at that position in string W.
- If the letter lt is part of the substring then it must be changed to some other character according to the above rules.
Examples:
Input : n = 3
s1 = "etr"
s2 = "ed"
s3 = "ied"
W = "PEtrUnited"
letter = "d"
Output : PDddUnitda
Input : n = 1
s1 = "PetrsDreamOh"
W = "PetrsDreamOh"
letter = h
Output : HhhhhHhhhhHa
Explanation:
Example 1: First character P does not belong to any of the substrings therefore it is not changed. The next three characters form the substring “etr” and are changed to “Ddd”. The next four characters do not belong to any of the forbidden substrings and remain unchanged. The next two characters form the substring “ed” and are changed to “da” since d is The last character itself, it is replaced with another character ‘a’ such that the string is lexicographically the smallest.
Notice: “Etr” = “etr” and the changed substring “Ddd” has first character as ‘D’ since first letter of “Etr” is in uppercase.
Example 2: Since the entire string is a forbidden string, it is replaced with letter ‘h’ from first to second last character according to the case. The last character is ‘h’ therefore it is replaced with letter ‘a’ such that the string is lexicographically the smallest.
Approach:
Check for every character of the string W, if it is the beginning of the any of the substrings or not. Use another array to keep record of the characters of W that are part of the forbidden strings and needs to be changed.
The characters are changed according to the following rules:
- If W[i] = letter and letter = ‘a’ then W[i] = ‘b’
- If W[i] = letter and letter !=’a’ then W[i] = ‘a’
- If W[i] != letter then W[i] = letter
The first and second condition will also be used when W[i] is an uppercase character.
Below is the implementation of the above approach:
C++
// CPP program to remove the forbidden strings#include <bits/stdc++.h>using namespace std;// pre[] keeps record of the characters// of w that need to be changedbool pre[100];// number of forbidden stringsint n;// given stringstring w;// stores the forbidden stringsstring s[110];// letter to replace and occur// max number of timeschar letter;// Function to check if the particula// r substring is present in w at positionvoid verify(int position, int index){ int l = w.length(); int k = s[index].length(); // If length of substring from this // position is greater than length // of w then return if (position + k > l) return; bool same = true; for (int i = position; i < position + k; i++) { // n and n1 are used to check for // substring without considering // the case of the letters in w // by comparing the difference // of ASCII values int n, n1; char ch = w[i]; char ch1 = s[index][i - position]; if (ch >= 'a' && ch <= 'z') n = ch - 'a'; else n = ch - 'A'; if (ch1 >= 'a' && ch1 <= 'z') n1 = ch1 - 'a'; else n1 = ch1 - 'A'; if (n != n1) same = false; } // If same == true then it means a // substring was found starting at // position therefore all characters // from position to length of substring // found need to be changed therefore // they needs to be marked if (same == true) { for (int i = position; i < position + k; i++) pre[i] = true; return; }}// Function implementing logicvoid solve(){ int l = w.length(); int p = letter - 'a'; for (int i = 0; i < 100; i++) pre[i] = false; // To verify if any substring is // starting from index i for (int i = 0; i < l; i++) { for (int j = 0; j < n; j++) verify(i, j); } // Modifying the string w // according to the rules for (int i = 0; i < l; i++) { if (pre[i] == true) { if (w[i] == letter) w[i] = (letter == 'a') ? 'b' : 'a'; // This condition checks // if w[i]=upper(letter) else if (w[i] == 'A' + p) w[i] = (letter == 'a') ? 'B' : 'A'; // This condition checks if w[i] // is any lowercase letter apart // from letter. If true replace // it with letter else if (w[i] >= 'a' && w[i] <= 'z') w[i] = letter; // This condition checks if w[i] // is any uppercase letter apart // from letter. If true then // replace it with upper(letter). else if (w[i] >= 'A' && w[i] <= 'Z') w[i] = 'A' + p; } } cout << w;}// Driver function for the programint main(){ n = 3; s[0] = "etr"; s[1] = "ed"; s[2] = "ied"; w = "PEtrUnited"; letter = 'd'; // Calling function solve(); return 0;} |
Java
// Java program to remove forbidden strings import java.io.*;class rtf { // number of forbidden strings public static int n; // original string public static String z; // forbidden strings public static String s[] = new String[100]; // to store original string // as character array public static char w[]; // letter to replace and occur // max number of times public static char letter; // pre[] keeps record of the characters // of w that need to be changed public static boolean pre[] = new boolean[100]; // Function to check if the particular // substring is present in w at position public static void verify(int position, int index) { int l = z.length(); int k = s[index].length(); // If length of substring from this // position is greater than length // of w then return if (position + k > l) return; boolean same = true; for (int i = position; i < position + k; i++) { // n and n1 are used to check for // substring without considering // the case of the letters in w // by comparing the difference // of ASCII values int n, n1; char ch = w[i]; char ch1 = s[index].charAt(i - position); if (ch >= 'a' && ch <= 'z') n = ch - 'a'; else n = ch - 'A'; if (ch1 >= 'a' && ch1 <= 'z') n1 = ch1 - 'a'; else n1 = ch1 - 'A'; if (n != n1) same = false; } // If same == true then it means a substring // was found starting at position therefore // all characters from position to length // of substring found need to be changed // therefore they need to be marked if (same == true) { for (int i = position; i < position + k; i++) pre[i] = true; return; } } // Function performing calculations. public static void solve() { w = z.toCharArray(); letter = 'd'; int l = z.length(); int p = letter - 'a'; for (int i = 0; i < 100; i++) pre[i] = false; // To verify if any substring is // starting from index i for (int i = 0; i < l; i++) { for (int j = 0; j < n; j++) verify(i, j); } // Modifying the string w // according to the rules for (int i = 0; i < l; i++) { if (pre[i] == true) { if (w[i] == letter) w[i] = (letter == 'a') ? 'b' : 'a'; // This condition checks // if w[i]=upper(letter) else if (w[i] == (char)((int)'A' + p)) w[i] = (letter == 'a') ? 'B' : 'A'; // This condition checks if w[i] // is any lowercase letter apart // from letter. If true replace // it with letter else if (w[i] >= 'a' && w[i] <= 'z') w[i] = letter; // This condition checks if w[i] // is any uppercase letter apart // from letter. If true then // replace it with upper(letter). else if (w[i] >= 'A' && w[i] <= 'Z') w[i] = (char)((int)'A' + p); } } System.out.println(w); } // Driver function for the program public static void main(String args[]) { n = 3; s[0] = "etr"; s[1] = "ed"; s[2] = "ied"; z = "PEtrUnited"; solve(); }} |
Python3
# Python program to remove the forbidden strings# pre[] keeps record of the characters# of w that need to be changedpre = [False]*100# stores the forbidden stringss = [None]*110# Function to check if the particula# r substring is present in w at positiondef verify(position, index): l = len(w) k = len(s[index]) # If length of substring from this # position is greater than length # of w then return if (position + k > l): return same = True for i in range(position, position + k): # n and n1 are used to check for # substring without considering # the case of the letters in w # by comparing the difference # of ASCII values ch = w[i] ch1 = s[index][i - position] if (ch >= 'a' and ch <= 'z'): n = ord(ch) - ord('a') else: n = ord(ch) - ord('A') if (ch1 >= 'a' and ch1 <= 'z'): n1 = ord(ch1) - ord('a') else: n1 = ord(ch1) - ord('A') if (n != n1): same = False # If same == true then it means a # substring was found starting at # position therefore all characters # from position to length of substring # found need to be changed therefore # they needs to be marked if (same == True): for i in range( position, position + k): pre[i] = True return# Function implementing logicdef solve(): l = len(w) p = ord(letter) - ord('a') # To verify if any substring is # starting from index i for i in range(l): for j in range(n): verify(i, j) # Modifying the string w # according to the rules for i in range(l): if (pre[i] == True): if (w[i] == letter): w[i] = 'b' if (letter == 'a') else 'a' # This condition checks # if w[i]=upper(letter) elif (w[i] == str(ord('A') + p)): w[i] = 'B' if (letter == 'a') else 'A' # This condition checks if w[i] # is any lowercase letter apart # from letter. If true replace # it with letter elif (w[i] >= 'a' and w[i] <= 'z'): w[i] = letter # This condition checks if w[i] # is any uppercase letter apart # from letter. If true then # replace it with upper(letter). elif (w[i] >= 'A' and w[i] <= 'Z'): w[i] = chr(ord('A') + p) print(''.join(w))# Driver function for the program# number of forbidden stringsn = 3s[0] = "etr"s[1] = "ed"s[2] = "ied"# given stringw = "PEtrUnited"w = list(w)# letter to replace and occur# max number of timesletter = 'd'# Calling functionsolve()# This code is contributed by ankush_953 |
C#
// C# program to remove forbidden strings using System;class GFG{// number of forbidden strings public static int n;// original string public static string z;// forbidden strings public static string[] s = new string[100];// to store original string // as character array public static char[] w;// letter to replace and occur // max number of times public static char letter;// pre[] keeps record of the characters // of w that need to be changed public static bool[] pre = new bool[100];// Function to check if the particular // substring is present in w at position public static void verify(int position, int index){ int l = z.Length; int k = s[index].Length; // If length of substring from this // position is greater than length // of w then return if (position + k > l) { return; } bool same = true; for (int i = position; i < position + k; i++) { // n and n1 are used to check for // substring without considering // the case of the letters in w // by comparing the difference // of ASCII values int n, n1; char ch = w[i]; char ch1 = s[index][i - position]; if (ch >= 'a' && ch <= 'z') { n = ch - 'a'; } else { n = ch - 'A'; } if (ch1 >= 'a' && ch1 <= 'z') { n1 = ch1 - 'a'; } else { n1 = ch1 - 'A'; } if (n != n1) { same = false; } } // If same == true then it means a // substring was found starting at // position therefore all characters // from position to length of substring // found need to be changed therefore // they need to be marked if (same == true) { for (int i = position; i < position + k; i++) { pre[i] = true; } return; }}// Function performing calculations. public static void solve(){ w = z.ToCharArray(); letter = 'd'; int l = z.Length; int p = letter - 'a'; for (int i = 0; i < 100; i++) { pre[i] = false; } // To verify if any substring is // starting from index i for (int i = 0; i < l; i++) { for (int j = 0; j < n; j++) { verify(i, j); } } // Modifying the string w // according to the rules for (int i = 0; i < l; i++) { if (pre[i] == true) { if (w[i] == letter) { w[i] = (letter == 'a') ? 'b' : 'a'; } // This condition checks // if w[i]=upper(letter) else if (w[i] == (char)((int)'A' + p)) { w[i] = (letter == 'a') ? 'B' : 'A'; } // This condition checks if w[i] // is any lowercase letter apart // from letter. If true replace // it with letter else if (w[i] >= 'a' && w[i] <= 'z') { w[i] = letter; } // This condition checks if w[i] // is any uppercase letter apart // from letter. If true then // replace it with upper(letter). else if (w[i] >= 'A' && w[i] <= 'Z') { w[i] = (char)((int)'A' + p); } } } Console.WriteLine(w);}// Driver Code public static void Main(string[] args){ n = 3; s[0] = "etr"; s[1] = "ed"; s[2] = "ied"; z = "PEtrUnited"; solve();}}// This code is contributed by Shrikanth13 |
Javascript
// JavaScript program to remove the forbidden strings// pre[] keeps record of the characters// of w that need to be changedlet pre = new Array(100).fill(false);let s = new Array(110);let w, letter;// Function to check if the particula// r substring is present in w at positionconst verify = (position, index) => { let l = w.length; let k = s[index].length; // If length of substring from this // position is greater than length // of w then return if (position + k > l) { return; } let same = true; for (let i = position; i < position + k; i++) { // n and n1 are used to check for // substring without considering // the case of the letters in w // by comparing the difference // of ASCII values let ch = w[i]; let ch1 = s[index][i - position]; let n, n1; if (ch >= 'a' && ch <= 'z') { n = ch.charCodeAt() - 'a'.charCodeAt(); } else { n = ch.charCodeAt() - 'A'.charCodeAt(); } if (ch1 >= 'a' && ch1 <= 'z') { n1 = ch1.charCodeAt() - 'a'.charCodeAt(); } else { n1 = ch1.charCodeAt() - 'A'.charCodeAt(); } if (n !== n1) { same = false; } } // If same == true then it means a // substring was found starting at // position therefore all characters // from position to length of substring // found need to be changed therefore // they needs to be marked if (same === true) { for (let i = position; i < position + k; i++) { pre[i] = true; } return; }};// Function implementing logicconst solve = () => { let l = w.length; let p = letter.charCodeAt() - 'a'.charCodeAt(); // To verify if any substring is // starting from index i for (let i = 0; i < l; i++) { for (let j = 0; j < n; j++) { verify(i, j); } } // Modifying the string w // according to the rules for (let i = 0; i < l; i++) { if (pre[i] === true) { if (w[i] === letter) { w[i] = letter === 'a' ? 'b' : 'a'; } // This condition checks // if w[i]=upper(letter) else if (w[i] === String.fromCharCode('A'.charCodeAt() + p)) { w[i] = letter === 'a' ? 'B' : 'A'; } // This condition checks if w[i] // is any lowercase letter apart // from letter. If true replace // it with letter else if (w[i] >= 'a' && w[i] <= 'z') { w[i] = letter; } // This condition checks if w[i] // is any uppercase letter apart // from letter. If true then // replace it with upper(letter). else if (w[i] >= 'A' && w[i] <= 'Z') { w[i] = String.fromCharCode('A'.charCodeAt() + p); } } } console.log(w.join(''));};// Driver function for the programlet n = 3;s[0] = "etr";s[1] = "ed";s[2] = "ied";w = "PEtrUnited".split('');letter = 'd';solve()//contributed by sdeadityasharma |
Output
PDddUnitda
Time Complexity: O(n)
Auxiliary Space: O(n)
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!
