涉及算法：动态规划（dp）

这是一个多状态的线性dp问题。
解题分析：
    字符串的长度是n，找到我们最后一个字符‘y’，假设它的下标是 i ，那么我们最终等结果就是 [0，i] 区间中的 "shy" 字符串的个数。
    而我们要求 [0，i] 区间中的 "shy" 字符串的个数，也就就是要求 [0, i - 1] 区间中字符串 "sh" 的个数。
    要求 [0, i - 1] 区间中字符串 "sh" 的个数，也就是要求 [0, i - 2] 区间中字符 's' 的个数
    所以我们只需要知道 i 位置的  's' 的个数，然后去求出"sh"的个数，从而得到"shy"  的个数即可。
解题思路：
    1. 状态表示：
        三个数组：s[ i ] , h[ i ] , y[ i ]    
        s[ i ] ：表示[0, i] 区间中字符 's' 的数量
        h[ i ] ：表示[0, i] 区间中字符 'sh' 的数量
        y[ i ] ：表示[0, i] 区间中字符 'shy' 的数量
那么最终结果就是 y[n - 1] 。
    2. 状态转移方程
    
    3. 初始化
         由于上面都是由 i -1 位置退出来的，所以我们只需要初始化第一个位置即可：
         对于s[0]，需要判断是否为 's' ，如是，则为1，如不是则为0.
         对于h[0]，和y[0]都初始为 0 ，因为第一个位置不可能是 "sh"或"shy"。
    4. 返回值
        y[n-1]即为最终结果。

空间优化
我们其实不需要真的创建数组，直接通过三个整型类型的变量就可以来表示对应位置的数目了。
    • s 表示遍历到当前位置 's' 的数量
    • h 表示遍历到当前位置 "sh" 的数量
    • y 表示遍历到当前位置 '"shy" 的数量
思路：
    • 如果 str[i] 等于 's' ，则s++；
    • 如果str[i] 等于 'h' ，则 h += s；
    • 如果str[i] 等于 'y' ，则 y += h； 
    • 遍历结束，y 中存的就是这个字符串中"shy"的个数，所以最后返回 y 即可。
下面我们就是以空间优化的思路来写的代码：
#include <iostream>
#include <string>
using namespace std;

int n;
string str;

int main()
{
    cin >> n >> str;
    
    long long s = 0, h = 0, y = 0;
    for(int i = 0; i < n; i++)
    {
        char ch = str[i];
        if(ch == 's') s++;
        else if(ch == 'h') h += s;
        else if(ch == 'y') y += h;
    }
    cout << y << endl;
    return 0;
}