【完美走位】

完美走位

题目描述：
输入一个长度为4的倍数的字符串，字符串中仅包含WASD四个字母。
将这个字符串中的连续子串用同等长度的仅包含WASD的字符串替换Q，如果替换后整个字符串中WASD四个字母出现的频数相同，那么我们称替换后的字符串是“完美走位”。求子串的最小长度。
如果输入字符串已经平衡则输出0。二、输入
一行字符表示给定的字符串s 数据范围：
1<=n<=10^5且n是4的倍数，字符串中仅包含WASD四个字母。三、输出一个整数表示答案四、样例输入输出示例1：输入：WASDAASD 输出：1 说明：
将第二个A替换为W，即可得到完美走位。示例2：输入：AAAA 输出：3 说明：
将其中三个连续的A替换为WSD，即可得到完美走位
思路分析：
1：先用一个map统计出字符串所有的字符个数，然后先看是否"完美"。
2：再利用经典的尺取法。
从左往右移动区间，当满足条件时，左端点右移，缩小区间，当不满足条件时，右端点右移，扩大区间，这样可以找到每个满足条件的区间，从而可以找到最小区间。
记录不包含该区间时WMASD的数量，先判断能否通过替换区间内的元素使WASD数量一致，再判断剩余位置是否是4的倍数。

#include<iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<exception> 
#include<map>
#include<cmath>
#include<unordered_map>
#include<set>
#include<climits>
#include<ctype.h>
#include<queue>
#include<stack>
#include<list>
using namespace std;
 
int main(){
    // 处理输入
    string input_str ;
    cin >> input_str;
 
    map<char, int> char_count;
    for (auto x : input_str) {
        if (char_count.count(x)) {
            char_count[x] +=1;
        } else {
            char_count[x] =1;
        }
    }
    
    // 特殊情况
    if (char_count['W'] == char_count['A']  &&
        char_count['W'] == char_count['S']  &&
        char_count['W'] == char_count['D']) {
            cout << 0;
            return 0;
        }
    
    // 左右区间位置 
    int left = 0;
    int right = 0;
    int length = 0;
    
    // 替换的最小长度
    int res = input_str.size();
    // 出现次数最多的字母
    int max_char_num = 0;
    // 可替换字母个数, 随着指针移动，如果free_char_num 大于0且能被4整除，当前范围满足条件，左指针右移一格，否则右指针右移
    int free_char_num = 0;
    
    char_count[input_str[0]]--;
    while (true)
    {
        max_char_num = max(max((max(char_count['W'], char_count['S'])), char_count['A']), char_count['D']);
        length = right - left + 1;
        free_char_num = length - ((max_char_num - char_count['W']) + (max_char_num - char_count['S']) + (max_char_num - char_count['A']) + (max_char_num - char_count['D']));
        if (free_char_num >= 0 && free_char_num % 4 == 0){
            if(length<res) {
                res = length;
            }
            char_count[input_str[left]]++;
            left++;
 
        } else {
            right++;
            char_count[input_str[right]]--;
        }
 
        if (right >= input_str.size())// 越界即结束
            break;
    }
    cout << res;
    return 0;
}