×

# 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.

# Time Complexity

$O(n)$

# Space Complexity

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

This question is marked "community wiki".

6★likecs
3.7k2481
accept rate: 9%

19.8k350498541

 0 Cant i initialize has[26]={0} like this instead of using for loop .. when i am using for loop its accepted but when doing like hash[26]={0},getting WA My code :https://ideone.com/41po2B plzz explain .. answered 27 Aug '17, 01:28 1 accept rate: 0% 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++. (27 Aug '17, 01:40) likecs6★
 0 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[26]; int[]brr=new int[26]; for (int i = 0; i < arr.length; i++) { arr[i]=sc.nextInt(); } String str=sc.next(); for(int j=0;j
 0 int main() { int t; cin>>t; while(t--) {int a[26]; string s; for(int i=0;i<26;i++) cin>>a[i]; cin>>s;  int sum=0; for(int j=0;j<26;j++) {int f=0; for(int k=0;k
 0 answered 30 Aug '17, 10:14 3★eugalt 282●7 accept rate: 4%
 0 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 price(26); vector flag(26, 0); string str;  answered 16 Oct '17, 23:55 4★faded4k 26●2 accept rate: 14%
 -2 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[26]; int[]brr=new int[26]; for (int i = 0; i < arr.length; i++) { arr[i]=sc.nextInt(); } String str=sc.next(); for(int j=0;j
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,688
×191
×64
×13

question asked: 24 Aug '17, 16:09

question was seen: 1,838 times

last updated: 16 Oct '17, 23:55