algorithm - How to find closed loop more efficiently -

i have following data structures , algorithms question i've been trying think better solution -

given

$x longitude , $y latitude

and following characters

'>' east $x++ ; '<' west $x-- ; '^' north $y++ ; 'v' south $y-- ;

and sample input string "^v<>><^>v<>^<^>^>>v>><^^<>><<<><<><^<^v<^^v<<>><<<<^>v^>v^v^<<>>v<><^<>><>>^><>v^v>v<<>v<>v^^><<>>>v<<>>>>^>v>>”

write function identifies closed loops (some samples given below examples of closed loop) [ “^v”, “<>”, “><“, “^>v<“, ... ]

i have been able solve in o(n^2) picking each character input given , going through entire string , keeping 2 count variables - 1 vertical count , horizontal count, @ point value on both 0 it's closed loop. wondering if there can more efficiently - maybe there's algorithm missing out.

thanks & regards, vaibhav

create bitset of arbitrary length, e.g. n.

define hashing function maps pair of x,y co-ordinates bit in bitset.

start @ beginning of string, initializing current x , y zero.

for each character, compute hash , check corresponding bit in bitset. if if set check if there loop ending @ current character, using current algorithm, working backwards. set bit current position, adjust x , y based on character , move onto next character.

the bitset serves quick check see whether loop possible ending @ current character, full check done in case bit set, avoid false positives in case of hash collisions, , find starting character of loop. allows handle more complex loops return same position more once (such figure 8 loop begins , ends @ cross), if want count them separately smaller loops contain.