max frequency of character in string

Question

#include<bits/stdc++.h>
#include<cstring>
#define arraySize 10

using namespace std;
char returnMaxOccur(char *str);

int main()
{
    char str[]="teet";
    cout<<"The max occuring character is"<<" "<<returnMaxOccur(str)<<endl;
    return 0;
}

char returnMaxOccur(char* str)
{
    int high=-1;
    char t;
    int counter[arraySize]={0};

    int len=strlen(str);

    for(int i=0;i<len;i++)
    {
        counter[str[i]]++;
    }


    for(int i=0;i<len;i++)
    {
        if(high<counter[str[i]])
        {
            high=counter[str[i]];
            t=str[i];
        }
    }
    return t;
}

In the following question when #include<bits/stdc++.h> is included the results for input string are as follows,

1)teet: ans is t  
2)eett: ans is e  
3)ttee: ans is t  
4)ette: ans is e

but when i include #include<iostream> instead of #include<bits/stdc++.h> the results are

1)teet: ans is e  
2)eett: ans is t  
3)ttee: ans is t  
4)ette: ans is e

what is the reason for this behaviour,or am i doing anything wrong?

http://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h — πάντα ῥεῖ, May 20 '17 at 11:13
`str[i]` is way larger than `arraysize` (10) -> you are invoking *undefined behavior* — UnholySheep, May 20 '17 at 11:13

score 6 · Accepted Answer · edited May 23 '17 at 10:31

This is a textbook case of how undefined behaviour can manifest in seemingly bizarre behaviour.

In practice, including different headers has likely affected what bytes are at certain positions in memory, bytes that you accidentally observe when you vastly overrun your array counter (size 10) with indexes that could go all the way up to 255.

The traditional way to approach this task is with a std::map<char, int>, which can effectively function as a "sparse array". Failing that, just make sure you have enough "slots" in your int[] for every possible input.

(And, IMO, you shouldn't be using bits/stdc++.h anyway.)

score 1 · Answer 2 · edited May 23 '17 at 10:31

1

The first important thing is that your code is not correct. Please correct it as follows:

Instead of

#define arraySize 10

use

#define arraySize 128

as str[i] may be arbitrary character (I suppose an ASCII character from 0 to 127)

and only then repeat your testing with changing the #include statement.

The second - and generally more important - was just expressed by πάντα ῥεῖ in his link (Why should I not #include ?)

edited May 23 '17 at 10:31

Community

1
1

answered May 20 '17 at 11:46

MarianD

13,096
12
42
54

This will help little when `str` contains letters (as in the OP's case). – Angew is no longer proud of SO May 20 '17 at 11:50
@Angew - I don't understand you - it changes incorrect code (out-of- bounds index) to the correct one in spite of symbols used in `str`. Note apostrophes around `0` in my replacement. – MarianD May 20 '17 at 11:54
`'t' - '0' > 9`, [see it live](http://coliru.stacked-crooked.com/a/e3eaf43ca174ecf0). Your fix would only help if `str` was restricted to digits. – Angew is no longer proud of SO May 20 '17 at 11:55
@Angew - Oh, you are right, thanks! I am going to edit my answer. – MarianD May 20 '17 at 11:57

score 0 · Answer 3 · answered May 20 '17 at 11:28

0

when i=0, counter[str[i]]++ is counter[116]++, but counter array size is 10. So the code counter[116]++ modifies an arbitrary memory address.

answered May 20 '17 at 11:28

wyc

351
2
11

max frequency of character in string

3 Answers3