How can I improve this code?

[Arslan7041]

So I wrote the following program which prompts the user to enter a string. It then outputs the character which was used the most number of times, as well as how many times it was used.

Here is it below;

#include <iostream>

using namespace std;

int main()
{

    string text;
    
    cout << "Type in a string: " << endl << endl;
    getline(cin, text);

    int cnt = 0;
    int maximum = 0;
    string letter;
    
    // This outer loop will go through each character
    // which all other character will be compared to
    for(int i=0; i<text.length(); i++)
    {
        for(int k = i; k<text.length(); k++) // Inner loop goes through each character to compare it to character from outer loop
        {
            if(text[k]== ' ') // spaces dont count as characters, hence they are skipped
                continue;
                
            if(text[i]==text[k] || toupper(text[i])==toupper(text[k])) // C++ is case sensitive. So both characters are made uppercase to ensure valid comparison. 
                   cnt++;
        }

        if(cnt > maximum)
        {
            maximum = cnt;
            letter = text[i];
        }

        cnt = 0; // cnt reset to 0 for the next comparison

    }

    cout << "\n\n";
    cout << "The character used most number of times: " << letter << endl;
    cout << "Number of times it was used: " << maximum << endl;

       for(int i=0; i<text.length(); i++)
    {
        cout << text[i];
        if(text[i]==letter || toupper(text[i])==toupper(letter))
        {
            cout << "*";
        }
    }

    cin.get();
}

My only question is: How can I improve this code? Is there a more efficient way to do this?

[18hRX9L8]

Line 24: Use continue instead. If I enter in two spaces, it will still register the second one.

http://en.cppreference.com/w/cpp/language/continue

[Arslan7041]

Not sure what you mean. Line 24 skips spaces only as Im not counting them as a character. It doesn't skip the next letter.

I just tried out the program using spaces, it works fine.

[Arslan7041]

Although continue; works just as well. So I changed it to that because it looks better.

Thank you.

Any other suggestions?

[18hRX9L8]

I edited my comment after further inspection.

[18hRX9L8]

https://en.wikipedia.org/wiki/Computational_complexity_theory

Your algorithm has a worst-case time complexity of O(n²) (two same-sized for loops).

Using a dictionary to store letters, the worst-case time complexity would be O(2n) (One for-loop iteration and one lookup iteration). Here is an example of what I'm talking about:

1 paragraph, 5 words, 27 bytes of Lorem Ipsum:

Your algorithm:

CPU time used: 0.04 ms
Wall clock time passed: 0.04 ms

Dictionary algorithm:

CPU time used: 0.07 ms
Wall clock time passed: 0.05 ms

1 paragraph, 50 words, 336 bytes of Lorem Ipsum

Your algorithm:

CPU time used: 4.49 ms
Wall clock time passed: 4.49 ms

Dictionary algorithm:

CPU time used: 0.11 ms
Wall clock time passed: 0.09 ms

5 paragraphs, 500 words, 3445 bytes of Lorem Ipsum

Your algorithm:

CPU time used: 393.50 ms
Wall clock time passed: 394.64 ms

Dictionary algorithm:

CPU time used: 0.58 ms
Wall clock time passed: 0.75 ms

57 paragraphs, 5000 words, 33745 bytes of Lorem Ipsum

Your algorithm:

CPU time used: 37569.21 ms
Wall clock time passed: 37847.68 ms

Dictionary algorithm:

CPU time used: 3.89 ms
Wall clock time passed: 3.89 ms

116 paragraphs, 10000 words, 67697 bytes of Lorem Ipsum

Your algorithm:

CPU time used: 151572.87 ms
Wall clock time passed: 153052.78 ms

Dictionary algorithm:

CPU time used: 6.60 ms
Wall clock time passed: 6.58 ms

As you can see in the tests, the dictionary algorithm's time-complexity doubled (2n) each test while your algorithm's time-complexity increased exponentially. Your users may not be happy if they have to wait 2.5 minutes to get their essays evaluated. (Note that I was testing with a 2.5GHz i5 and 16GB of ram, most users are going to be running your program on something slower.)

For reference, I have included the dictionary algorithm I was using:

for (char i : text) {
	if (!isspace(i)) {
		letters[i]++;
	}
}

std::unordered_map<char, unsigned>::iterator max = std::max_element(letters.begin(), letters.end(),
	[](const std::pair<char, unsigned>& p1, const std::pair<char, unsigned>& p2) {
		return p1.second < p2.second;
	}
);

[Arslan7041]

Did not really understand the code in your last post, as im not that advanced. Can you offer something a bit simpler?

Also not sure why your posts are all reported?

[ne555]

> Line 24: k++;. This is technically correc
No, line 24 is plain wrong.

$ ./a.out
Type in a string: 

a  b  c  d  e  f


The character used most number of times:  
Number of times it was used: 5

> cin.get();
I prefer a program that ends when it terminates.

[Arslan7041]

Sorry, thats not the output I get when I type in that user input.

I get "a" as most used character, being used 1 times. Dont know why you got something different.

I prefer a program that ends when it terminates.

I thought cin.get(); was better than system("PAUSE")? Or are you saying I should just replace it with return 0?

[ne555]

That output is with your first code.
Note that there are two spaces between each letter.


> Or are you saying I should just replace it with return 0?
yes

[Arslan7041]

That output is with your first code.
Note that there are two spaces between each letter.

Ah, I see. So I guess the difference between k++ and continue is that with k++ it simply increments k and then moves on to the next if-statement directly below it, but with continue it reiterates the loop with incremented k and so the same initial if-statement is tested again, thereby testing for multiple spaces.

Thank you for that bit of insight.