sarthak_brahma's blog

By sarthak_brahma, history, 3 years ago, In English

If the number of T is not double of M, then "NO". If the first or last character is M, then "NO".

I made two arrays that had the count of T's from the right and from the left. Then I traversed the string and for every M, I checked if the number of T's on left and right are positive or not. (To achieve this I had another variable which had the count of 'M' processed) `

vector<int> right(n), left(n);
    left[0] = 1;
    right[n &mdash; 1] = 1;
    for (int i = 1; i < n; i++)
    {
        if (s[i] == 'T')
            left[i] = left[i &mdash; 1] + 1;
        else
            left[i] = left[i &mdash; 1];
    }

    for (int i = n - 2; i >= 0; i--)
    {
        if (s[i] == 'T')
            right[i] = right[i + 1] + 1;
        else
            right[i] = right[i + 1];
    }

    int mp = 0;


    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'M')
        {
            int l = left[i] - mp;
            int r = right[i] - mp;

            if (l > 0 && r > 0)
            {
                mp++;
            }
            else
            {
                cout << "NO\n";
                f = true;
                break;
            }
        }
    }

`

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it