Counting the proportion of vowels in substrings I'm looking for an algorithm to make my code faster and better for big strings.

Problem link

Let the simple prettiness of a string be the count of vowels (I, E, A, O, U, Y) divided by the length of the string.  Find the sum of the simple prettiness of all substrings of a given string (with precision within 1 part per million), where the input string may be up to 5∙105.

Let's say I have the following input:

IEAIAIO


The output should be like this:

28.000000


Second ex:

BYOB
5.833333


Third ex:

YISVOWEL
17.050000


My solution gives me Time Limited Exceeded on big strings.

#include &lt;bits/stdc++.h&gt;
using namespace std;
int main()
{

    string s;
    while (cin&gt;&gt;s)
    {

        long double sum=0.0;

        for (int i = 0; i &lt; s.length(); i++)
        {
            for (int j = i+1; j &lt;= s.length(); j++)
            {
                string ss=s.substr(i,j-i);
                //&lt;&lt;ss&lt;&lt;endl;
                long double len=0.0;
                for (int r = 0; r &lt; ss.length(); r++)
                {
                    if(ss[r]=='I' || ss[r]=='E' || ss[r]=='A' || ss[r]=='O' || ss[r]=='U' || ss[r]=='Y' )
                        len++;
                }
                //cout&lt;&lt;"len = "&lt;&lt;len&lt;&lt;"\tss= "&lt;&lt;ss&lt;&lt;endl;
                long double len_ss=ss.length();
                sum+=(len/len_ss);
            }
        }
        cout&lt;&lt;fixed;
        cout &lt;&lt; std::setprecision(6) &lt;&lt; sum&lt;&lt;endl;

    }
return 0;

}
Style

You probably don't care much about this but your style (spacing for instance) is not very consistent.

Making things easier to improve

You'll make your code much easier to improve if :


you have a way to measure performances
you have a way to ensure you don't screw it up.


You can do so by writing a few tests.

#include &lt;assert.h&gt;
#include &lt;bits/stdc++.h&gt;
using namespace std;

long double prettyness(const string &amp; s)
{
    long double sum = 0.0;
    long double len_s = s.length();
    for (int i = 0; i &lt; len_s; i++)
    {
        for (int j = i+1; j &lt;= len_s; j++)
        {
            string ss = s.substr(i,j-i);
            long double len = 0.0;
            long double len_ss = ss.length();
            for (int r = 0; r &lt; len_ss; r++)
            {
                if(ss[r]=='I' || ss[r]=='E' || ss[r]=='A' || ss[r]=='O' || ss[r]=='U' || ss[r]=='Y' )
                    len++;
            }
            sum += len/len_ss;
        }
    }
    return sum;
}

void stdio_tests()
{
    string s;
    while (cin&gt;&gt;s)
    {
        cout &lt;&lt; fixed &lt;&lt; std::setprecision(6) &lt;&lt; prettyness(s) &lt;&lt; endl;
    }
}

void unit_tests()
{
    long double res;
    res = prettyness("IEAIAIO");
    assert(res == 28);
    res = prettyness("BYOB");
    assert(5.83333 &lt; res &amp;&amp; res &lt; 5.83334);
    res = prettyness("YISVOWEL");
    assert(17.04 &lt; res &amp;&amp; res &lt; 17.06);
    res = prettyness("QWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNM");
    assert(79984 &lt; res &amp;&amp; res &lt; 79985);
}

int main()
{
    unit_tests();
    return 0;
}


Improvements

I already got rid of the multiples calls to length() above. Let's try to make other improvements.

For a start, you don't need to use substr at all. You can simply try to be smart with string indices :

long double prettyness(const string &amp; s)
{
    long double sum = 0.0;
    long double len_s = s.length();
    for (int i = 0; i &lt; len_s; i++)
    {
        for (int j = i+1; j &lt;= len_s; j++)
        {
            long double len = 0.0;
            for (int r = i; r &lt; j; r++)
            {
                if(s[r]=='I' || s[r]=='E' || s[r]=='A' || s[r]=='O' || s[r]=='U' || s[r]=='Y' )
                    len++;
            }
            sum += len/(j-i);
        }
    }
    return sum;
}


Then, you can get rid of the multiple checks of the char value by storing the result in an array.

Also, you could make things much faster by storing cumulative sums of vowels so that you can get number of vowels in substring i..j by computing something like cum[j]-cum[i].

The code would be something like :

long double prettyness(const string &amp; s)
{
    long double sum = 0.0;
    size_t len_s = s.length();
    long double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i &lt; len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');
    for (int i = 0; i &lt; len_s; i++)
        for (int j = i+1; j &lt;= len_s; j++)
            sum += (cum[j]-cum[i])/(j-i);
    return sum;
}


This is much faster but I'm pretty sure there is a way to do better. For instance, substrings of same lengths could be considered together to perform a smaller number of divisions.

long double prettyness(const string &amp; s)
{
    size_t len_s = s.length();
    double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i &lt; len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');
    long double sum = 0.0;
    for (int l = 1; l &lt;= len_s; l++)
    {
        long double tmp_sum = 0.0;
        for (int end = l; end &lt;= len_s; end++)
        {
            tmp_sum += cum[end] - cum[end-l];
        }
        sum += tmp_sum/l;
    }
    return sum;
}


Then, some trick to compute the inside of the loop faster. Indeed, many indices cancel each other. At the end, you are down to some value that can be precomputed with another cumulative array :

long double prettyness(const string &amp; s)
{
    size_t len_s = s.length();
    double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i &lt; len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');

    double cum_cum[len_s + 2];
    cum_cum[0] = 0;
    for (int i = 0; i &lt;= len_s; i++)
        cum_cum[i + 1] = cum_cum[i] + cum[i];

    long double sum = 0.0;
    for (int l = 1; l &lt;= len_s; l++)
        sum += (cum_cum[len_s + 1] - cum_cum[l] - cum_cum[len_s - l + 1])/l;
    return sum;
}


You have a O(n) algorithm, that should be fast enough (and it is easy to see that better complexity cannot be achieved).