题解

题面描述

给定一个长度为$n$的字符串$s$（$s$仅包含字符$'<'$和$'>'$），其中字符$'<'$代表向左移动，$'>'$代表向右移动。对于每个起始位置$i$（$0 \le i < n$），小红按照顺序依次执行$s_i, s_{i+1}, s_{i+2}, \dots$中的指令，但不必执行到字符串末尾。要求判断是否存在某个非空前缀，使得执行后小红能够回到原点（即净位移为$0$）。对于每个$i$，输出$1$表示存在这种可能，输出$0$表示不存在。

思路

题目内容

小红在一维度的世界中，她可以向左或者向右移动。她拿到一个长度为$n$的字符串$s$，仅包含'$<$'和'$>$' 两种字符，'$<$' 表示向左移动，'$>$'表示向右移动。

小红想知道，如果从字符串$s$的第$i(0≤i<n)$个字符开始,然后按照$S_i,S_{i+1},S_{i+2},...$的顺序依次移动，那么小红有没有机会回到原地。

值得注意的是，你需要对于任意的$i(0≤i<n)$ 都判断是否存在一种移动方式，使得小红可以回到原地且不一定需要执行到$s_{n-1}$，每个$i$的判断互不影响。

输入描述

第一行一个整数$n(1≤n≤2×10^5)$,表示字符串s的长度。

第二行一个字符串$s$，仅包含'$<$'和'$>$'两种字符。

输出描述

输出$n$个整数，第$i$个整数表示从第$i$个字符开始移动，小红有没有机会回到原地，若有机会输出$1$，否则输出$0$。

样例1

输入

4
><><

输出

1 1 1 0

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写