Using Flowgorithm

Question

Design a program that prompts the user to enter a string , and displays the character that appears most frequently in the string.

Answer 1

The python algorithm posted by Phil uses two loops to give you the answer, which results in O(n2) time complexity and O(1) space complexity.

The following Java code achieves the same with O(n) time complexity (it can be done in Python too), since it requires only a single pass through the input string. In order to achieve that we will need to store character counts for each letter.

import java.util.Scanner;

public class MostFrequentCharacter {

private static char getMostFrequentChar(String str) {

int[] charCount = new int[128];

int max = 0;

char result = '\0';

for (int i = 0; i < str.length(); i++) {

int val = str.charAt(i);

charCount[val]++;

if (max < charCount[val]) {

max = charCount[val];

result = (char)val;

}

}

return result;

}

public static void main(String[] args) {

System.out.print("Enter a string: ");

String inputString = new Scanner(System. in).nextLine();

char result = getMostFrequentChar(inputString);

System.out.print("Most frequently used character: " + result);

}

}

Answer 2

I like Python. Its a simple language. Here's the code I would use. Remember that in programming, there could be many ways to solve the same problem.

word = input("Enter any word: ")

highest = 0

count = 0

letterMost = ""

for letterTest in word:

for letter in word:

if letterTest == letter:

count = count +1

if count > highest:

highest = count

letterMost = letter

count = 0

print("The letter",letterMost,"appears",highest,"times")

Answer 3

#include <iostream>

#include <string>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#define MAX_INBUFF_SIZE (2048)

typedef struct _TCharCount

{

int count;

char chChar;

} *TCharCount;

#define CHAR_COUNT_SIZE (sizeof(struct _TCharCount))

int compareCharCount( const void * rec1, const void * rec2)

{

TCharCount charCountRec1 = (TCharCount) rec1;

TCharCount charCountRec2 = (TCharCount) rec2;

return (charCountRec1->count - charCountRec2->count);

}

int PromptForString( char * inBuff, char * promptMsg)

{

string inbuff;

cout << "******************************************************" << endl;

cout << promptMsg << " :> ";

getline(cin,inbuff);

memset(inBuff,0,MAX_INBUFF_SIZE);

strncpy(inBuff,inbuff.c_str(),MAX_INBUFF_SIZE-1);

//flushes the input buffer and eats the newline

//cin.ignore(MAX_INBUFF_SIZE,'\n');

return(strlen(inBuff));

}

//returns the most frequently occuring character in str

// ... but if there is a TIE, return '2'

// ... if there is a 3-way tie, returns '3',

// if there is a 4-eay tie, returns '4'...

// etc...

void countChars ( char * str, int * Freq)

{

int n = strlen(str);

char ch;

for (int iLoop=0; iLoop<n; iLoop++)

{

ch = str[iLoop];

if (

(( ch >='A') && (ch <='Z')) ||

(( ch >='a') && (ch <='z'))

)

{

ch = toupper(ch);

Freq[ch-65]++;

}

} //for

}

void GetWinners(char * chResults, int * Freq)

{

struct _TCharCount freq[26];

char chChar;

for (int iLoop=0; iLoop<26; iLoop++)

{

freq[iLoop].count = Freq[iLoop];

chChar=char(iLoop+65);

freq[iLoop].chChar = chChar;

cout << "xfer " << chChar << " to "<< freq[iLoop].chChar << endl;

cout << "freq " << freq[iLoop].count << endl;

}

qsort(freq,26,CHAR_COUNT_SIZE,compareCharCount);

int maxCount = freq[25].count;

int iIndexPos = 25;

int i=0;

cout << " cophying results" << endl;

while (freq[iIndexPos].count >=maxCount)

{

chResults[i] = freq[iIndexPos].chChar;

cout << " transferring " << freq[iIndexPos].chChar << " to " << chResults[i] << endl;

iIndexPos--; i++;

}

}

int main()

{

char inbuff[MAX_INBUFF_SIZE];

int Freq[26];

char chWinners[26];

memset(inbuff,0,MAX_INBUFF_SIZE);

memset(Freq,0,sizeof(int)*26);

countChars(inbuff,Freq);

int n = PromptForString(inbuff,(char *)"Please input the string ");

if (n>0)

{

countChars(inbuff,Freq);

memset(chWinners,0,26);

GetWinners(chWinners,Freq);

int i=0;

char * chPtr = chWinners;

while (*chPtr)

{

putchar(*chPtr); cout << " ";

chPtr++;

}

}

}