Intermediate.
Put your skills to the test.

Problem summary

A mermaid chooses a starting position in a row. A < current forces a move left, > forces a move right, and * allows either direction. Find the maximum number of moves before leaving the row, or −1 if she can remain indefinitely.

Constraints

1 ≤ n ≤ 20; characters are <, >, and *.

Worked example

The worked example illustrates the rule described in the analysis.

5
*****
4
<<<>

-1
3

Solution analysis

1. An infinite journey exists exactly when some adjacent cells allow movement in both directions. The left cell permits right unless it is <; the right cell permits left unless it is >.
2. If such an adjacent pair exists, alternate forever. If none exists, the row has a prefix of < characters, at most one *, and a suffix of > characters.
3. In the finite case, starting at the most favourable location yields max(number of <, number of >)+number of * moves, including the final move to shore. Five * cells allow an infinite journey, while <<<> permits three moves.

Why it works

A finite directed path graph can contain a directed cycle only across an adjacent pair with both directions enabled. Without such a pair, all paths flow towards one shore; the longest uses the longer forced-direction block and the optional neutral cell.

Watch out. Include the final move outside the row. Check both characters of an adjacent pair. There are exactly two cases, without a leading test count.

An independently written complete program with standard headers.

// Key idea: A finite directed path graph can contain a directed cycle only across an adjacent pair
// with both directions enabled. Without such a pair, all paths flow towards one shore; the longest
// uses the longer forced-direction block and the optional neutral cell.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
    for(int test=0;test<2;++test){
        int n;
        string current;
        cin>>n>>current;
        bool infinite=false;
        for(int i=0;i+1<n;++i){
            if(current[i]!='<'&&current[i+1]!='>'){
                infinite=true;
            }
        }
        int left=0,right=0,neutral=0;
        for(char direction:current){
            left+=direction=='<';
            right+=direction=='>';
            neutral+=direction=='*';
        }
        cout<<(infinite?-1:max(left,right)+neutral)<<'\n';
    }
}