CENSTR - EDITORIAL

PROBLEM LINK:

Contest
Practice

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();
    }
}