CareerCup

@Shashi... Well I didn't got why U are doing the last if check
if(S[i]=='?'){
S[i]='A';
}

This makes logic highly vulnerable..
Example..:-
You are always replacing last character with alphabet 'A' if its '?' why ??

Processing from the end of a string is not always a solution, consider following example:
S: AKTAK??????
p: AKTAK

if we start for the end of the string, than result will contain only 2 substrings: AKTAKAAKTAK
but if we'll move forward, we'll have 3 substrings: AKTAKTAKTAK

Working Code ....

{
string fillString(string s, string w){
    int m,i;
    m=s.size()-1;
    i = w.size()-1;
    bool flag = false;
    int start,cur;
    while(m>-1){
        
        if(s[m]==w[i] || s[m]=='?'){
            start = flag ? start : m;
            i--;
            flag = true;
        }
        else{
            m = flag ? start : m;
            flag=false;
            i = w.size()-1;
        }
        if(i==-1 && flag == true){
            cur=m; i=0;
            while(cur<=start){
                s[cur++]=w[i++];
            }
            flag = false;
            i = w.size()-1;
        }
        m--;
    }
    cur=s.size()-1;
    while(cur>-1){
        if(s[cur]=='?')s[cur]='A';
        cur--;
    }
    return s;
}

}

i think the logic is same as of shashi. time complexity min O(n) max O(n*m)

shashi:
can u please explain the logic

If we write same code for java it throws StringIndexOutOfBounds so in the if statement you just have to check if k>=0 so that error doesnt appear.

This is how it works.
1. Get the length of String s and p
2. start comparing from the end of String s and String p if you find two chars are equal or ? then keep comparing
3. if the whole string p is in S then replace all those ? with the characters of p.
4. If p is not part of S then just add the first character of p for that character and decrements the index by i--

How about this?

class CCID15259735 {
	// ST [11:21] ET [11:30]
	public static void q1(){
		String S = "ABAAMA????MAZON????????";
		String P = "AMAZON";
		
		// String S ="?????";
		// String P ="ABCD";
		
		for(int i=0; i< S.length();i++){
			int k = i;
			char thisChar;
			boolean isPinS = true;
			for(int posInP = 0; posInP < P.length() && k < S.length(); posInP++){
				thisChar = S.charAt(k);
				if(thisChar == '?' || thisChar == P.charAt(posInP)){
					k++;
					continue;
				}
				isPinS = false;
				break;
			}
			
			if(isPinS && (k-i) == P.length()){
				System.out.println("Fill [i][" + i + "] till [k][" + k + "] of S = " + S.substring(i, k));
				i = k; // Once matched then progress i to k.
			}
		}
	}
}

Idea: may be we can apply kmp with a small modification?

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int main() {
    char s[] = "ABAAMA????MAZON????????";
    char t[] = "AMAZON";

    int j = 0;
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == t[j]) {
            j++;
            j = j % strlen(t);
        }
        if (s[i] == '?') {
            s[i] = t[j++];
            j = j % strlen(t);
        }
    }

    cout << s;
    
    /* It Prints -- "ABAAMAZONAMAZONAMAZONAM"
     */

}

I think following algorithm should be applied:
When we find several ? symbols in the middle of the string, we should calculate
a) How much symbols should be appended to the left of ???? to complement p string.
b) How much symbols should be appended to the right of ???? to complement p string.
if a<b - append symbols to the left.

For example:
S: TERR????RRA
p: TERRA

step #1: TERRA???RRA
step #2: TERRA?TERRA

Repeat algorithm till we have any ? symbol in the S string.

How is the string "ABAAMAZONAMAZONAAAMAZON" lexicographically sorted? COuld someone please explain the question to me?

public static char[] fillString(char[] str1, char[] str2){
int flag1 = 0;
int flag2 = 0;
for(int i=0;i<str1.length;i++){
System.out.println(str1[i]);
if(flag1>0){ // check the next in series
if(str1[i]=='?'){
if(flag1==str2.length)
flag1=0;
str1[i]= str2[flag1];
flag1++;
System.out.println("===="+flag1);
continue;
}
if(str1[i]==str2[flag1]){
flag1++;
System.out.println("===="+flag1);
continue;
}
}
if(str1[i]==str2[0]){ // check the first character
flag1=1;
System.out.println("===="+flag1);
continue;
}
if(str1[i]=='?'){ // if no match in string is present before
if(flag2==str2.length)
flag2=0;
str1[i]=str2[flag2];
System.out.println("+++++"+flag2);
flag2++;
continue;
}
}
return str1;
}

// Str1 = "ABAAMA?????MAZON??????????AMA??????????????????"
// Str2 = "AMAZON"

want to have your precious feedback, about the complexity and otherthings .. Please review it and let me know

work with both examples
{{
static String fillString(String S, String p){
StringBuilder SB = new StringBuilder(S);
int skip = p.length()-1;
boolean keep = false;
for (int i = SB.length()-1; i >= 0; i--){
if (SB.charAt(i) == '?'){
SB.setCharAt(i, p.charAt(skip));
skip--;
if (skip < 0){
if (keep) skip = p.length()-1;
else skip = 0;
}
}
else {
if (!keep) {
skip = p.length()-1;
keep = true;
}
if (SB.charAt(i) == p.charAt(skip)){
skip--;
if (skip < 0) skip = p.length()-1;
}
else {
skip = p.length()-1;
keep = false;
}
}
}
return SB.toString();
}}

works with both examples:

static String fillString(String S, String p){
		StringBuilder SB = new StringBuilder(S);
		int skip = p.length()-1;
		boolean keep = false;
		for (int i = SB.length()-1; i >= 0; i--){
			if (SB.charAt(i) == '?'){
				SB.setCharAt(i, p.charAt(skip));
				skip--;
				if (skip < 0){
					if (keep) skip = p.length()-1;
					else skip = 0;
				}
			}
			else {
				if (!keep) {
					skip = p.length()-1;
					keep = true;
				}
				if (SB.charAt(i) == p.charAt(skip)){
					skip--;
					if (skip < 0) skip = p.length()-1;
				}
				else { 
					skip = p.length()-1;
					keep = false;
				}
			}
		}
		return SB.toString();

// Sorry for duplicated answer