Remove the forbidden strings - Coding

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 changed
bool pre[100];
 
// number of forbidden strings
int n;
 
// given string
string w;
 
// stores the forbidden strings
string s[110];
 
// letter to replace and occur
// max number of times
char letter;
 
// Function to check if the particula
// r substring is present in w at position
void 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 logic
void 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 program
int 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 changed
pre = [False]*100
 
# stores the forbidden strings
s = [None]*110
 
# Function to check if the particula
# r substring is present in w at position
def 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 logic
def 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 strings
n = 3
 
s[0] = "etr"
s[1] = "ed"
s[2] = "ied"
 
# given string
w = "PEtrUnited"
w = list(w)
 
# letter to replace and occur
# max number of times
letter = 'd'
 
# Calling function
solve()
 
 
# 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 changed
let 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 position
const 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 logic
const 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 program
let 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)

Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Smallest number with sum of digits as N and divisible by 10^N
Sum of f(a[i], a[j]) over all pairs in an array of n integers
Check if it is possible to convert one string into another with given constraints
Smallest number with sum of digits as N and divisible by 10^N
Smallest number with sum of digits as N and divisible by 10^N

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12