Given string S of size N consisting of K distinct characters and (N – K) ‘?’s, the task is to replace all ‘?’ with existing characters from the string such that every substring of size K has consisted of unique characters only. If it is not possible to do so, then print “-1”.
Examples:
Input: S = “????abcd”, K = 4
Output: abcdabcd
Explanation:
Replacing the 4 ‘?’s with “abcd” modifies string S to “abcdabcd”, which satisfies the given condition.Input: S = “?a?b?c”, K = 3
Output: bacbac
Explanation:
Replacing S[0] with ‘b’, S[2] with ‘c’ and S[4] with ‘a’ modifies string S to “bacbac”, which satisfies the given condition.
Approach: The idea is based on the observation that in the final resultant string, each character must appear after exactly K places, like the (K + 1)th character must be the same as 1st, (K + 2)th character must be the same as 2nd, and so on.
Follow the steps below to solve the problem:
- Initialize a hashmap M to store the positions of characters.
- Traverse the string S using the variable i and if the current character S[i] is not the same as ‘?‘, then update M[i % K] = S[i].
- Traverse the string S using the variable i and if the value of i%k is not present in map M, then print “-1” and break out of the loop. Else update S[i] to M[i % K].
- After the above steps, if the loop doesn’t break, then print S as the resultant string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to replace all '?'// characters in a string such// that the given conditions are satisfiedvoid fillString(string s, int k){ unordered_map<int, char> mp; // Traverse the string to Map the // characters with respective positions for (int i = 0; i < s.size(); i++) { if (s[i] != '?') { mp[i % k] = s[i]; } } // Traverse the string again and // replace all unknown characters for (int i = 0; i < s.size(); i++) { // If i % k is not found in // the Map M, then return -1 if (mp.find(i % k) == mp.end()) { cout << -1; return; } // Update S[i] s[i] = mp[i % k]; } // Print the string S cout << s;}// Driver Codeint main(){ string S = "????abcd"; int K = 4; fillString(S, K); return 0;} |
Java
// Java Program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to replace all '?' // characters in a string such // that the given conditions are satisfied static void fillString(String str, int k) { char s[] = str.toCharArray(); HashMap<Integer, Character> mp = new HashMap<>(); // Traverse the string to Map the // characters with respective positions for (int i = 0; i < s.length; i++) { if (s[i] != '?') { mp.put(i % k, s[i]); } } // Traverse the string again and // replace all unknown characters for (int i = 0; i < s.length; i++) { // If i % k is not found in // the Map M, then return -1 if (!mp.containsKey(i % k)) { System.out.println(-1); return; } // Update S[i] s[i] = mp.getOrDefault(i % k, s[i]); } // Print the string S System.out.println(new String(s)); } // Driver Code public static void main(String[] args) { String S = "????abcd"; int K = 4; fillString(S, K); }}// This code is contributed by Kingash. |
Python3
# Python 3 program for the above approach# Function to replace all '?'# characters in a string such# that the given conditions are satisfieddef fillString(s, k): mp = {} # Traverse the string to Map the # characters with respective positions for i in range(len(s)): if (s[i] != '?'): mp[i % k] = s[i] # Traverse the string again and # replace all unknown characters s = list(s) for i in range(len(s)): # If i % k is not found in # the Map M, then return -1 if ((i % k) not in mp): print(-1) return # Update S[i] s[i] = mp[i % k] # Print the string S s = ''.join(s) print(s)# Driver Codeif __name__ == '__main__': S = "????abcd" K = 4 fillString(S, K) # This code is contributed by bgangwar59. |
C#
// C# program for the above approach using System;using System.Collections.Generic; class GFG { // Function to replace all '?' // characters in a string such // that the given conditions are satisfied static void fillString(string str, int k) { char[] s = str.ToCharArray(); Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the string to Map the // characters with respective positions for (int i = 0; i < s.Length; i++) { if (s[i] != '?') { mp[i % k] = s[i]; } } // Traverse the string again and // replace all unknown characters for (int i = 0; i < s.Length; i++) { // If i % k is not found in // the Map M, then return -1 if (!mp.ContainsKey(i % k)) { Console.WriteLine(-1); return; } // Update S[i] s[i] = (char)mp[i % k]; } // Print the string S Console.WriteLine(new string(s)); } // Driver code static void Main() { string S = "????abcd"; int K = 4; fillString(S, K); }}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script> // JavaScript program for the above approach // Function to replace all '?' // characters in a string such // that the given conditions are satisfied function fillString(str, k) { var s = str.split(""); var mp = {}; // Traverse the string to Map the // characters with respective positions for (var i = 0; i < s.length; i++) { if (s[i] !== "?") { mp[i % k] = s[i]; } } // Traverse the string again and // replace all unknown characters for (var i = 0; i < s.length; i++) { // If i % k is not found in // the Map M, then return -1 if (!mp.hasOwnProperty(i % k)) { document.write(-1); return; } // Update S[i] s[i] = mp[i % k]; } // Print the string S document.write(s.join("") + "<br>"); } // Driver code var S = "????abcd"; var K = 4; fillString(S, K); </script> |
Output:
abcdabcd
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!
