题目描述
给你两个字符串 s 和 t ，请你通过若干次以下操作将字符串 s 转化成字符串 t ：
选择 s 中一个 非空 子字符串并将它包含的字符就地 升序 排序。 比方说，对下划线所示的子字符串进行操作可以由 "14234" 得到 "12344" 。
如果可以将字符串 s 变成 t ，返回 true 。否则，返回 false 。
一个 子字符串 定义为一个字符串中连续的若干字符。
示例 1
输入：s = "84532", t = "34852"
输出：true
解释：你可以按以下操作将 s 转变为 t ：
"84532" （从下标 2 到下标 3）-> "84352"
"84352" （从下标 0 到下标 2） -> "34852"
示例 2
输入：s = "34521", t = "23415"
输出：true
解释：你可以按以下操作将 s 转变为 t ：
"34521" -> "23451"
"23451" -> "23415"
示例 3
输入：s = "12345", t = "12435"
输出：false
示例 4
输入：s = "1", t = "2"
输出：false
提示：
s.length == t.length
1 <= s.length <= 105
s 和 t 都只包含数字字符，即 '0' 到 '9' 。
解
如果想把s变成t，那么我们需要找到第一个不相等的位置x，这个位置的t值为tx，然后在s中找到第一次出现的tx，想办法把tx移到x去（因为只能升序排序，所以这里只可能是s中第一个出现的tx，后面的tx移不到前面）。刚开始想的是直接对s从x到第一次出现tx的位置排序，然后发现过不了样例1。
为了保证前面的操作不影响之后的结果，我们可以通过不断的让tx和前面一位数进行排序把tx移到合适的位置，如样例一就可以通过84532->84352->83452->38452->34852得到结果。因为每一位数字移动后其他数字的位置关系并没有发生变化，所以前面的操作并不会影响之后的结果。如果s能变换成t，通过重复这种方法一定可以实现。
也不需要真的把值移到前面去，直接改成一个特殊值标记为使用过之后遇到直接跳过就行。
然后超时了。。。接下去就有点面向数据编程了，发现超时的数据是很多连续重复值的，于是设了个cnt变量对连续的相同值统一处理。
虽然a了但应该不算正常解法，大概可以通过队列存一下数字出现位置直接判断队列达到O(10*n)复杂度。但心有点累就懒得写了。
class Solution {
public:
bool isTransformable(string s, string t) {
int n=s.size();
for(int i=0,k=0;i<n;i++,k++)
{
while(!s[k])k++;
if(s[k]==t[i])continue;
int cnt=1;
while(t[i]==t[i+cnt])cnt++;
i+=cnt-1;
for(int j=k;j<n;j++)
{
if(!s[j])continue;
if(s[j]==t[i])
{
s[j]=0;
cnt--;
if(cnt==0)
break;
}
else if(s[j]<t[i])return 0;
}
if(cnt)
return 0;
k--;
}
return 1;
}
};