Given two strings s1 and s2(all letters in uppercase). Check if it is possible to convert s1 to s2 by performing following operations.
- Make some lowercase letters uppercase.
- Delete all the lowercase letters.
Examples:
Input : s1 = daBcd s2 = ABC Output : yes Explanation : daBcd -> dABCd -> ABC Convert a and b at index 1 and 3 to upper case, delete the rest those are lowercase. We get the string s2. Input : s1 = argaju s2 = RAJ Output : yes Explanation : argaju -> aRgAJu -> RAJ convert index 1, 3 and 4 to uppercase and then delete. All lowercase letters Input : s1 = ABcd s2= BCD Output : NO
Approach:
Let DPi, j be 1 if it is possible to convert 1st i characters of s1 to j characters of s2, else DPi, j=0. Close observations gives us two conditions to deal with.
Initially DP0, 0=1, if DPi, j=1 then it is possible to check for next sets using following conditions.
- If s1[i] in upper case is equal to s2[j] then it is possible to convert i+1 characters of s1 to j+1 characters of s2, hence DPi+1, j+1=1.
- If s1[i] is in lower case, then it is possible to delete that element and hence i+1 characters can be converted to j characters of s2. Hence DPi+1, j=1.
If DPn, m=1, then it is possible to convert s1 to s2 by following conditions.
Below is the CPP illustration of the above approach.
C++
// cpp program to check if a string can// be converted to another string by// performing operations#include <bits/stdc++.h>using namespace std;// function to check if a string can be// converted to another string by// performing following operationsbool check(string s1, string s2){ // calculates length int n = s1.length(); int m = s2.length(); bool dp[n + 1][m + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { dp[i][j] = false; } } // mark 1st position as true dp[0][0] = true; // traverse for all DPi, j for (int i = 0; i < s1.length(); i++) { for (int j = 0; j <= s2.length(); j++) { // if possible for to convert i // characters of s1 to j characters // of s2 if (dp[i][j]) { // if upper_case(s1[i])==s2[j] // is same if (j < s2.length() && (toupper(s1[i]) == s2[j])) dp[i + 1][j + 1] = true; // if not upper then deletion is // possible if (!isupper(s1[i])) dp[i + 1][j] = true; } } } return (dp[n][m]);}// driver codeint main(){ string s1 = "daBcd"; string s2 = "ABC"; if (check(s1, s2)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java program to check if a string can// be converted to another string by// performing operationsimport java.io.*;class GFG { // function to check if a string can be // converted to another string by // performing following operations static boolean check(String s1, String s2) { // calculates length int n = s1.length(); int m = s2.length(); boolean dp[][]=new boolean[n + 1][m + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { dp[i][j] = false; } } // mark 1st position as true dp[0][0] = true; // traverse for all DPi, j for (int i = 0; i < s1.length(); i++) { for (int j = 0; j <= s2.length(); j++) { // if possible for to convert i // characters of s1 to j characters // of s2 if (dp[i][j]) { // if upper_case(s1[i])==s2[j] // is same if (j < s2.length() && (Character.toUpperCase(s1.charAt(i)) == s2.charAt(j))) dp[i + 1][j + 1] = true; // if not upper then deletion is // possible if (!Character.isUpperCase(s1.charAt(i))) dp[i + 1][j] = true; } } } return (dp[n][m]); } // driver code public static void main(String args[]) { String s1 = "daBcd"; String s2 = "ABC"; if (check(s1, s2)) System.out.println("YES"); else System.out.println("NO"); }}// This code is contributed by Nikita Tiwari. |
Python3
# Python3 program to check if a string can # be converted to another string by # performing operations # function to check if a string can be # converted to another string by # performing following operations def check(s1,s2): # calculates length n = len(s1) m = len(s2) dp=([[False for i in range(m+1)] for i in range(n+1)]) # mark 1st position as true dp[0][0] = True # traverse for all DPi, j for i in range(len(s1)): for j in range(len(s2)+1): # if possible for to convert i # characters of s1 to j characters # of s2 if (dp[i][j]): # if upper_case(s1[i])==s2[j] # is same if ((j < len(s2) and (s1[i].upper()== s2[j]))): dp[i + 1][j + 1] = True # if not upper then deletion is # possible if (s1[i].isupper()==False): dp[i + 1][j] = True return (dp[n][m])# driver code if __name__=='__main__': s1 = "daBcd" s2 = "ABC" if (check(s1, s2)): print("YES") else: print("NO")# this code is contributed by # sahilshelangia |
C#
// C# program to check if a string can// be converted to another string by// performing operationsusing System;class GFG {// function to check if a string can be// converted to another string by// performing following operationsstatic bool check(string s1, string s2){ // calculates length int n = s1.Length; int m = s2.Length; bool[,] dp = new bool[n + 1, m + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { dp[i, j] = false; } } // mark 1st position as true dp[0, 0] = true; // traverse for all DPi, j for (int i = 0; i < s1.Length; i++) { for (int j = 0; j <= s2.Length; j++) { // if possible for to convert i // characters of s1 to j characters // of s2 if (dp[i, j]) { // if upper_case(s1[i])==s2[j] // is same if (j < s2.Length && (Char.ToUpper(s1[i]) == s2[j])) dp[i + 1, j + 1] = true; // if not upper then deletion is // possible if (!Char.IsUpper(s1[i])) dp[i + 1, j] = true; } } } return (dp[n, m]);}// Driver Codepublic static void Main(){ string s1 = "daBcd"; string s2 = "ABC"; if (check(s1, s2)) Console.Write("YES"); else Console.Write("NO");}}// This code is contributed // by ChitraNayal |
Javascript
<script>// Javascript program to check if a string can// be converted to another string by// performing operations // function to check if a string can be // converted to another string by // performing following operations function check(s1,s2) { // calculates length let n = s1.length; let m = s2.length; let dp=new Array(n + 1); for (let i = 0; i <= n; i++) { dp[i]=new Array(m+1); for (let j = 0; j <= m; j++) { dp[i][j] = false; } } // mark 1st position as true dp[0][0] = true; // traverse for all DPi, j for (let i = 0; i < s1.length; i++) { for (let j = 0; j <= s2.length; j++) { // if possible for to convert i // characters of s1 to j characters // of s2 if (dp[i][j]) { // if upper_case(s1[i])==s2[j] // is same if (j < s2.length && (s1[i].toUpperCase() == s2[j])) dp[i + 1][j + 1] = true; // if not upper then deletion is // possible if (!(s1[i] == s1[i].toUpperCase())) dp[i + 1][j] = true; } } } return (dp[n][m]); } // driver code let s1 = "daBcd"; let s2 = "ABC"; if (check(s1, s2)) document.write("YES"); else document.write("NO"); // This code is contributed by avanitrachhadiya2155</script> |
Output
YES
Time Complexity: O(N*M) where N and M are the lengths of the strings.
Auxiliary Space: O(N*M)
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!
