PROBLEM LINK:
Setter: Vidhi Shah, Hussain Pettiwala
Tester: Huzaifa Khilawala
DIFFICULTY
Easy
PROBLEM
Hussain wants to display words uniquely outside his shop chef cities. He wishes to highlight the word W by placing the letters vertically and centrally aligned but the problem is that he has to choose the letters from a string S given to him. Help him find if he can highlight the word from the given string.
Note:
- The letter of the word must be strictly centrally aligned
- All the letters of string S should be used only once
- Assume input to be lowercase.
EXPLANATION
For a string S “chefcitiesisthebest” and W being “eth”, he can get substrings as “chefc”, “iti” and “esisthebest”.
Billboard :
c H e f c
i t i
e s i s t h e b e s t
Here we are basically checking for the 1st occurrence of the ith letter in W and with the help of pointers calculate the number of the letters before that. Take the same number of letters ahead of the ith letter of W in S and form a substring. Increase the ith value by 1 and change the location of the pointer as well.
Keep checking if all letters of W are present in the center of the substring found. Use memoization to keep track of the already checked substrings.
SOLUTION
Setter's Solution
//Author : Hussain Pettiwala
hashed = {}
def check(b, a):
if (b, a) in hashed:
return hashed[(b, a)]
if len(a) == 0 and len(b) == 0:
hashed[(b,a)] = True
return True
if len(b) == 0:
hashed[(b,a)] = False
return False
if len(a) == 0:
hashed[(b,a)] = False
return False
for j in range((len(a)-1)//2 + 1):
if a[j] == b[0]:
atemp = a[j*2+1:]
if check(b[1:], atemp):
hashed[(b,a)] = True
return True
hashed[(b,a)] = False
return False
if __name__ == '__main__':
for i in range(int(input())):
hashed = {}
a = input()
b = input()
print("True" if check(b, a) else "False")
Tester's Solution
import java.util.*;
class Codechef
{
public static boolean check(String b, String a, HashMap<String,Boolean> hm)
{
if(hm.containsKey(a+" "+b)) return hm.get(a+" "+b);
if (a.length()==0 && b.length()==0){
hm.put(a+" "+b,true);
return true;
}
if (b.length()==0 || a.length()==0){
hm.put(a+" "+b,false);
return false;
}
for (int j=0;j<(a.length()-1)/2+1;j++)
{
if (a.charAt(j)==b.charAt(0))
{
String atemp = a.substring(j*2+1);
if (check(b.substring(1),atemp,hm)){
hm.put(a+" "+b,true);
return true;
}
}
}
hm.put(a+" "+b,false);
return false;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int testcase = Integer.parseInt(sc.nextLine());
for(int i=0;i<testcase;i++){
String a = sc.nextLine();
String b = sc.nextLine();
HashMap<String,Boolean> hm = new HashMap<String,Boolean>();
System.out.println(check(b,a,hm)?"True":"False");
}
sc.close();
}
}