 # MATPAN - Editorial

Author: Alexandru Valeanu
Editorialist: Bhuvnesh Jain

CAKEWALK

# Prerequisites

Looping Techniques

# Problem

You are given a string consisting of letters and the cost of adding a specific character to it. You need to convert the string into a pangram, i.e. it contains all the lower case alphabets (a-z) in it. The cost of above operation is to be minimised.

# Explanation

For this subtask, N = 1. This means the string contains only 1 lower case character. So, we would need to add all the remaining characters so that it becomes pangram. To minimise the cost, it is easy to see that we would add each character only once.

Similar to above solution, we would like to only add those characters which are missing in the substring so that it becomes a pangram. Also, each character should be added only once to minimise the cost.

Thus, we need to find efficiently which characters occur in the string and which do not. To do this, we just maintain an array, of size equal to the alphabet size (in this case 26), such that all of it’s value are initialised to 0. Now, we simply traverse the array from left to right and set the corresponding character to 1 in the array. Thus, at the end of the loop, we just need to find the location of 0 in the above array and add the corresponding cost of the character to the answer.

O(n)

# Space Complexity

O(n + ALPHABET), where ALPHABET = number of lowercase characters (here 26)

1 Like

import java.util.Scanner;

``````class pangram {
public static void main(String[] args)throws Exception {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T--!=0) {
int[]arr=new int;
int[]brr=new int;
for (int i = 0; i < arr.length; i++) {
arr*=sc.nextInt();
}
String str=sc.next();
for(int j=0;j<str.length();j++) {
char ch=str.charAt(j);
brr[(int)ch-97]++;
}
int sum=0;
for(int i=0;i<arr.length;i++) {
if(brr*==0)
sum=sum+arr*;
}
System.out.println(sum);

}

}

}``````

Cant i initialize has={0} like this instead of using for loop …
when i am using for loop its accepted but when doing like hash={0},getting WA

My code :https://ideone.com/41po2B
plzz explain …

import java.util.Scanner;

class pangram {
public static void main(String[] args)throws Exception {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T–!=0) {
int[]arr=new int;
int[]brr=new int;
for (int i = 0; i < arr.length; i++) {
arr*=sc.nextInt();
}
String str=sc.next();
for(int j=0;j<str.length();j++) {
char ch=str.charAt(j);
brr[(int)ch-97]++;
}
int sum=0;
for(int i=0;i<arr.length;i++) {
if(brr*==0)
sum=sum+arr*;
}
System.out.println(sum);

``````    }

}
``````

}

int main()
{
int t;
cin>>t;
while(t–)
{int a;
string s;
for(int i=0;i<26;i++)
cin>>a*;
cin>>s;

``````	int sum=0;
for(int j=0;j<26;j++)
{int f=0;
for(int k=0;k<s.size();k++)
{
if(s[k]==(97+j))
{cout<<s[k]<<"+_";
f=1;
}

if(f==1)
break;

}
if(f==0)

sum=sum+a[j];

}

cout<<sum<<endl;
}
``````

}

I’m getting a weird problem with this problem. The same program, when the strings,vectors are defined as global outside any function, I get wrong answer but when I put them inside the main() function I get correct answer.
Language:c++14
Just put outside main function and you get WA. HOW AND WHY?

``````vector<int> price(26);
vector<int> flag(26, 0);
string str;
``````

Yes, you can do that, but in your case you are assigning particular index (26) to 0, which could have also lead to runtime error as size of array you declared is also 26. I have modified the code, which can can see here. Btw, i would suggest you to use memset or fill in C++.