below i have this java find my cat algorithm, and it has a run time of o(n^2), now how can i change the implementation to have a faster run time of o(n)

please explain what you did,

thanks

my code:

1 public class findcat 2 { 3 static void countCat(String str) 4 { 5 int count=0; 6 7 // search for pattern "((" 8 for (int i = 0; i < str.length() - 1; i++) 9 { 10 if (str.substring(i, i + 2).equals("((")) 11 { 12 13 // Search for pattern "))" if found "((" in outer loop 14 for (int j=i+2; j < str.length() - 1;j++){ 15 if (str.substring(j, j + 16 2).equals("))")){ 17 count=count+1; 18 } 19 } 20 } 21 } 22 23 System.out.println(count); 24 } 25 26 27 public static void main(String[] args) 28 { 29 String str1 = "(())(())(()"; 30 countCat(str1); 31 } 32 }