CODEWITHSUNDEEP
c++stringsubstring
Kaushik Mahadevan
Kaushik Mahadevan

Reputation: 89

Why does this code output different results for the same inputs?

I wrote a simple program to find the longest sub-string with distinct characters in a given string in C++. My code works for certain inputs, but doesn't for others. Moreover, it gives me different outputs for the same inputs. Where am I going wrong?

int main() {
    int t;
    cin >>t;
    while(t--){
        string s;
        cin >> s;
        int n = s.length();
        int maxlen = 0;
        for(int i = 0; i < n; i++){
            int count = 0;
            int arr[26] = {0};
            bool isDist = true;
            int j = i;
            while(isDist){
                if(arr[(int)s[j] - (int)'a'] == 0){
                    count++;
                    arr[(int)s[j] - (int)'a'] = 1;
                    j++;
                } else {
                    isDist = false;
                } 
            }
            if(count > maxlen) maxlen = count;
        }
        cout << maxlen << endl;
    }
    return 0;
}

for the following input:

3
aewergrththy
aewergrththy
aewergrththy

My code outputs:

5
4
4

Any help is appreciated, Thank you!

Upvotes: 0

Views: 257

Answers (2)

paddy
paddy

Reputation: 63481

The program has undefined behavior because you do not bounds-test when iterating over the string with j. You should modify the inner loop to test for j in addition to isDist:

while(isDist && j < n)

Without this, it's very easy for j to shoot past the end of the string as soon as all remaining characters in the string have not yet been encountered.

In this case, it will be when you process the character 'y' at the end of the string. After dealing with 'y', you'll advance j such that s[j] returns the string terminator. Now, you'll be accessing the array with arr[0 - 'y'] which of course is undefined behavior due to being a negative index.

Upvotes: 1

john
john

Reputation: 88017

The problem is that there is no check that j remains less than n, so you start checking characters beyond the end of your string, leading to in unpredictable results. Try

while (isDist && j < n)

That should help but I haven't checked the rest of your code for errors.

You could also consider using s.at(j) instead of s[j]. That at least results in predictable behaviour when going out of bounds, at throws an exception in that case.

Upvotes: 1

Related Questions