Friday, November 9, 2007

Strings

Problem Statement: Strings
I couldn't verify my answer coz it's from an IIT site - no solution verifier. So I'm just posting my algo, not the code...

Key:
n : number of chars per string
k : number of strings
alpha[] : a 26 element int array which stores the number of occurrences of each alphabet in a column

input n,k;
input the strings;
for i = 1 to n { //for each character
for j = 1 to k { //for each string
InitAlpha();
alpha[strs[j][i]-'a']++;
}
noOfM += FindNoOfMaxAlpha();
dist += k - alpha[FindMaxAlpha()];
}

InitAlpha()
{
for i=1 to 26
alpha[i] = 0;
}

FindMaxAlpha() //returns index (a=1,b=2,...) of the alphabet that has occurred max times in arr alpha[]
{
max = 0;
maxAlpha = 0; //index of alphabet that occurs max no of times
for i = 1 to 26 {
if alpha[i] > max {
max = alpha[i]
maxAlpha = i;
}
}
return i;
}

/* FindNoOfMaxAlpha()
* if only one char occurs max times in alpha[] returns 1
* otherwise, if there are >1 chars which occur max times, returns the no of such chars
*/
FindNoOfMaxAlpha()
{
noOfMax = 0;
max = 0;
for i = 1 to k {
if (alpha[i] > max) {
max = alpha[i];
noOfMax = 1;
}
else if (alpha[i] == max) noOfMax++;
}
return noOfMax;
}

2 comments:

Leslie Hope said...

Aargh! All the tabs stripped by Blogger..

Dileep P G said...

To defeat the stripper Blogger, enclose your code in preformatting html tags - "pre"

Contributors