Given a string S of length N consisting of lowercase English alphabets and ‘?’, the task is to check if it is possible to make the string non-decreasing by replacing all the ‘?’ characters with English alphabets. If found to be true, print “Yes”. Otherwise, print “No”.
Examples:
Input: S = “abb?xy?”
Output: Yes
Explanation:
Replacing the ‘?’s at index 3 and 6 with ‘b’ and ‘z’, modifies the string S to “abbbxyz”, which is non-decreasing.Input: S = “??z?a?”
Output : No
Naive Approach: The simplest approach to solve the problem is to generate all possible strings using English alphabets and check if the resulting string is non-decreasing or not. If found to be true, print “Yes”, Otherwise, print “No”.
Time Complexity: O(N*26N)
Auxiliary Space: O(N)
Efficient Approach: The given problem can be solved based on the following observations:
- It can be observed that the only position that matters is the position with S[i]! = ‘?’, as one can replace the ‘?’ with the character at the nearest index that is not ‘?’.
- Therefore, the task is reduced to checking if characters of the strings that are not ‘?’, are in non-decreasing order or not.
Follow the steps below to solve the problem:
- Initialize a variable, say last, to store the last character which is not a ‘?’.
- Traverse the string and for every ith character, check if S[i]! = ‘?’ and S[i]<last, then print “No”.
- Otherwise, update last as last = S[i] if S[i]!=’?’.
- Print “Yes” if none of the above cases are satisfied.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it's possible// to make the string s non decreasingint nonDecreasing(string s){ // Stores length of string int size = s.length(); // Stores the last character // that is not '?' char c = 'a'; // Traverse the string S for (int i = 0; i < size; i++) { // If current character // of the string is '?' if (s[i] == '?') { continue; } // If s[i] is not '?' // and is less than C else if ((s[i] != '?') && (s[i] < c)) { return 0; } // Otherwise else { // Update C c = s[i]; } } // Return 1 return 1;}// Driver Codeint main(){ string S = "abb?xy?"; if (nonDecreasing(S)) cout << "Yes" << endl; else cout << "No" << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check if it's possible// to make the String s non decreasingstatic int nonDecreasing(char []s){ // Stores length of String int size = s.length; // Stores the last character // that is not '?' char c = 'a'; // Traverse the String S for (int i = 0; i < size; i++) { // If current character // of the String is '?' if (s[i] == '?') { continue; } // If s[i] is not '?' // and is less than C else if ((s[i] != '?') && (s[i] < c)) { return 0; } // Otherwise else { // Update C c = s[i]; } } // Return 1 return 1;}// Driver Codepublic static void main(String[] args){ String S = "abb?xy?"; if (nonDecreasing(S.toCharArray())==1) System.out.print("Yes" +"\n"); else System.out.print("No" +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# python 3 program for the above approach# Function to check if it's possible# to make the string s non decreasingdef nonDecreasing(s): # Stores length of string size = len(s) # Stores the last character # that is not '?' c = 'a' # Traverse the string S for i in range(size): # If current character # of the string is '?' if (s[i] == '?'): continue # If s[i] is not '?' # and is less than C elif((s[i] != '?') and (s[i] < c)): return 0 # Otherwise else: # Update C c = s[i] # Return 1 return 1# Driver Codeif __name__ == '__main__': S = "abb?xy?" if(nonDecreasing(S)): print("Yes") else: print("No") # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to check if it's possible // to make the String s non decreasing static int nonDecreasing(char []s) { // Stores length of String int size = s.Length; // Stores the last character // that is not '?' char c = 'a'; // Traverse the String S for (int i = 0; i < size; i++) { // If current character // of the String is '?' if (s[i] == '?') { continue; } // If s[i] is not '?' // and is less than C else if ((s[i] != '?') && (s[i] < c)) { return 0; } // Otherwise else { // Update C c = s[i]; } } // Return 1 return 1; } // Driver Code public static void Main(String[] args) { String S = "abb?xy?"; if (nonDecreasing(S.ToCharArray())==1) Console.Write("Yes" +"\n"); else Console.Write("No" +"\n"); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to check if it's possible// to make the String s non decreasingfunction nonDecreasing(s){ // Stores length of String let size = s.length; // Stores the last character // that is not '?' var c = 'a'; // Traverse the String S for(let i = 0; i < size; i++) { // If current character // of the String is '?' if (s[i] == '?') { continue; } // If s[i] is not '?' // and is less than C else if ((s[i] != '?') && (s[i] < c)) { return 0; } // Otherwise else { // Update C c = s[i]; } } // Return 1 return 1;}// Driver Codelet S = "abb?xy?";if (nonDecreasing(S.split(''))) document.write("Yes" + "\n");else document.write("No" + "\n");// This code is contributed by shivanisinghss2110 </script> |
Output:
Yes
Time Complexity: O(N)
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
