Decode the Secret Heist Code
Berlin and Professor are on a secret heist mission, They have a secret code that’s the code which will signal Berlin to enter the building and initiate the heist. The plan is that the professor will write a word of random characters on his board. If removing characters from the word will give the secret code then it’s time for Berlin to shine (initiate the heist) but remember If one character is removed then it’s all existences in the word will be removed.
As Berlin is short temper he can initiate the mission if he is unable to decode the word, that’s why the professor needs your help to write a code that will take a word, the word written on the board, and the code, the secret code for the signal and return “Yes” if it’s time to initiate the mission or “No” if he still needs to wait.
Examples:
Input: word = “bhbalcbdkqgegr”, code = “hacker”
Output: Yes
Explanation: If we remove all existence of b, l, d, q, and g .we will get our code “hacker”Input: word = “acheranobylkl”, code = “chernobyl“
Output: No
Explanation: If we remove all existence of a and k, we will get “chernobyll” which has an extra “l” at the end which cannot be removed, as removing that will remove all existence of “l”.
Naive Approach: The basic way to solve the problem is as follows:
The idea is to iterate through the string “word” and whenever we get a character that is also present in the “code” we will add it to the “decoded” string. After the iteration, if the decoded string comes exactly the same as the code then we will return “Yes” otherwise “No”.
Below is the implementation of the above idea.
C++
// C++ code for the above approach: #include <iostream> #include <string> using namespace std; // Function to decode the word based // on the provided code string decoding(string word, string code) { string decoded = "" ; // Iterate through each character // in the word for ( char i : word) { // Check if the character is // present in the code if (code.find(i) != string::npos) { // Add the character to // the decoded string decoded += i; } } // Check if the decoded string is // equal to the code if (decoded == code) { // Return "YES" if the decoded string // matches the code return "YES" ; } else { // Return "NO" if the decoded string // does not match the code return "NO" ; } } // Drivers code int main() { // Input word and code string word = "bhbalcbdkqgegr" ; string code = "hacker" ; // Call the decoding function // and print the result cout << decoding(word, code) << endl; return 0; } |
Java
// Java code for the above approach: import java.util.*; public class GFG { public static void main(String[] args) { // Input word and code String word = "bhbalcbdkqgegr" ; String code = "hacker" ; // Call the decoding function // and print the result System.out.println(decoding(word, code)); } // Function to decode the word based // on the provided code public static String decoding(String word, String code) { String decoded = "" ; // Iterate through each character // in the word for ( char i : word.toCharArray()) { // Check if the character is // present in the code if (code.indexOf(i) != - 1 ) { // Add the character to // the decoded string decoded += i; } } // Check if the decoded string is // equal to the code if (decoded.equals(code)) { // Return "YES" if the decoded string // matches the code return "YES" ; } else { // Return "NO" if the decoded string // does not match the code return "NO" ; } } } // This code is contributed by Sakshi |
Python3
# Python3 implementation of above approach def decoding(word, code): #Initialize an empty string to store the decoded characters decoded = "" #iteration the word string for i in word: # Check if the character is present in the given secreat code if i in code: # Add the character to the decoded string decoded + = i # Check if the decoded string is equal to the given code if decoded = = code: #yes if both are same return "YES" else : #no if both are not same return "NO" # Driver Code word = "bhbalcbdkqgegr" code = "hacker" #Call the decoding function and print the result print (decoding(word, code)) # This code is contributed by the Author |
C#
// C# implementation using System; public class GFG { public static void Main( string [] args) { // Input word and code string word = "bhbalcbdkqgegr" ; string code = "hacker" ; // Call the decoding function // and print the result Console.WriteLine(decoding(word, code)); } // Function to decode the word based // on the provided code public static string decoding( string word, string code) { string decoded = "" ; // Iterate through each character // in the word foreach ( char i in word.ToCharArray()) { // Check if the character is // present in the code if (code.IndexOf(i) != -1) { // Add the character to // the decoded string decoded += i; } } // Check if the decoded string is // equal to the code if (decoded.Equals(code)) { // Return "YES" if the decoded string // matches the code return "YES" ; } else { // Return "NO" if the decoded string // does not match the code return "NO" ; } } } // This code is contributed by Sakshi |
Javascript
// Function to decode the word based // on the provided code function decoding(word, code) { let decoded = "" ; // Iterate through each character // in the word for (let i of word) { // Check if the character is // present in the code if (code.includes(i)) { // Add the character to // the decoded string decoded += i; } } // Check if the decoded string is // equal to the code if (decoded === code) { // Return "YES" if the decoded string // matches the code return "YES" ; } else { // Return "NO" if the decoded string // does not match the code return "NO" ; } } // Input word and code let word = "bhbalcbdkqgegr" ; let code = "hacker" ; // Call the decoding function // and print the result console.log(decoding(word, code)); |
YES
Time Complexity: O(N),
Auxiliary Space: O(N), where N is the length of the word string.
Efficient Approach: To solve the problem using Two Pointers follow the below idea:
In place of storing the value that matches the “code,” we will use a second pointer which will be shifted as we iterate through the “word” string until we reach the end of “word” or “code”.
Below is the implementation of the above idea.
C++
#include <iostream> #include <string> using namespace std; string decoding(string word, string code) { int word_index = 0; // Index for iterating through the word int code_index = 0; // Index for iterating through the code // Iterate until we reach the end of either the word or the code while (word_index < word.length() && code_index < code.length()) { // If the current characters in word and code match, move both pointers forward if (word[word_index] == code[code_index]) { word_index++; code_index++; } else { // If the characters don't match, move only the word pointer forward word_index++; } } // Check if we have reached the end of the word if (word_index == word.length()) { // Check if we have reached the end of the code if (code_index == code.length()) { // Return "YES" if all characters in the word are found in the code return "YES" ; } else { // Return "NO" if the code has additional characters return "NO" ; } } else { // If we are not at the end of the word, iterate through the remaining characters in the word while (word_index < word.length()) { // If any character in the word is found in the code, return "NO" if (code.find(word[word_index]) != string::npos) { return "NO" ; } word_index++; } // Return "YES" if no character in the word is found in the code // after we get the code string in the first while loop return "YES" ; } } // Driver Code int main() { string word = "bhbalcbdkqgegr" ; string code = "hacker" ; cout << decoding(word, code) << endl; return 0; } |
Java
public class GFG { public static String decoding(String word, String code) { int wordIndex = 0 ; // Index for iterating through the word int codeIndex = 0 ; // Index for iterating through the code // Iterate until we reach the end of either the word or the code while (wordIndex < word.length() && codeIndex < code.length()) { // If the current characters in word and code match, move both pointers forward if (word.charAt(wordIndex) == code.charAt(codeIndex)) { wordIndex++; codeIndex++; } else { // If the characters don't match, move only the word pointer forward wordIndex++; } } // Check if we have reached the end of the word if (wordIndex == word.length()) { // Check if we have reached the end of the code if (codeIndex == code.length()) { // Return "YES" if all characters in the word are found in the code return "YES" ; } else { // Return "NO" if the code has additional characters return "NO" ; } } else { // If we are not at the end of the word, iterate through the remaining characters in the word while (wordIndex < word.length()) { // If any character in the word is found in the code, return "NO" if (code.contains(String.valueOf(word.charAt(wordIndex)))) { return "NO" ; } wordIndex++; } // Return "YES" if no character in the word is found in the code // after we get the code string in the first while loop return "YES" ; } } public static void main(String[] args) { String word = "bhbalcbdkqgegr" ; String code = "hacker" ; System.out.println(decoding(word, code)); } } |
Python3
def decoding(word, code): word_index = 0 # Index for iterating through the word code_index = 0 # Index for iterating through the code # Iterate until we reach the end of either the word or the code while word_index < len (word) and code_index < len (code): # If the current characters in word and code match, move both pointers forward if word[word_index] = = code[code_index]: word_index + = 1 code_index + = 1 else : # If the characters don't match, move only the word pointer forward word_index + = 1 # Check if we have reached the end of the word if word_index = = len (word): # Check if we have reached the end of the code if code_index = = len (code): # Return "YES" if all characters in the word are found in the code return "YES" else : # Return "NO" if the code has additional characters return "NO" else : # If we are not at the end of the word, iterate through the remaining characters in the word while word_index < len (word): # If any character in the word is found in the code, return "NO" if word[word_index] in code: return "NO" word_index + = 1 # Return "YES" if no character in the word is found in the code # after we get the code string in the first while loop return "YES" # Driver Code word = "bhbalcbdkqgegr" code = "hacker" print (decoding(word, code)) |
C#
using System; class Program { static string Decoding( string word, string code) { int wordIndex = 0; // Index for iterating through the word int codeIndex = 0; // Index for iterating through the code // Iterate until we reach the end of either the word or the code while (wordIndex < word.Length && codeIndex < code.Length) { // If the current characters in word and code match, move both pointers forward if (word[wordIndex] == code[codeIndex]) { wordIndex++; codeIndex++; } else { // If the characters don't match, move only the word pointer forward wordIndex++; } } // Check if we have reached the end of the word if (wordIndex == word.Length) { // Check if we have reached the end of the code if (codeIndex == code.Length) { // Return "YES" if all characters in the word are found in the code return "YES" ; } else { // Return "NO" if the code has additional characters return "NO" ; } } else { // If we are not at the end of the word, iterate through the remaining characters in the word while (wordIndex < word.Length) { // If any character in the word is found in the code, return "NO" if (code.Contains(word[wordIndex].ToString())) { return "NO" ; } wordIndex++; } // Return "YES" if no character in the word is found in the code // after we get the code string in the first while loop return "YES" ; } } static void Main() { string word = "bhbalcbdkqgegr" ; string code = "hacker" ; Console.WriteLine(Decoding(word, code)); // Keep the console window open Console.ReadLine(); } } |
Javascript
function decoding(word, code) { let wordIndex = 0; // Index for iterating through the word let codeIndex = 0; // Index for iterating through the code // Iterate until we reach the end of either the word or the code while (wordIndex < word.length && codeIndex < code.length) { // If the current characters in word and code match, move both pointers forward if (word[wordIndex] === code[codeIndex]) { wordIndex++; codeIndex++; } else { // If the characters don't match, move only the word pointer forward wordIndex++; } } // Check if we have reached the end of the word if (wordIndex === word.length) { // Check if we have reached the end of the code if (codeIndex === code.length) { // Return "YES" if all characters in the word are found in the code return "YES" ; } else { // Return "NO" if the code has additional characters return "NO" ; } } else { // If we are not at the end of the word, iterate through the remaining characters in the word while (wordIndex < word.length) { // If any character in the word is found in the code, return "NO" if (code.includes(word[wordIndex])) { return "NO" ; } wordIndex++; } // Return "YES" if no character in the word is found in the code // after we get the code string in the first while loop return "YES" ; } } // Driver Code const word = "bhbalcbdkqgegr" ; const code = "hacker" ; console.log(decoding(word, code)); |
YES
Time Complexity: O(N), where N is the length of the word string.
Auxiliary Space: O(1).