Find length of longest symmetric substring

I have a string of characters '<', '>', '?' for example <><??>> . Now I want to find the longest symmetric substring (first half letters are < and last half letters are >) by replacing ? with < or >

Case 1:
For example input string <><??>>, the longest can be obtained as <><<<>>. In this symmetric substring is <<>> which is of length 4.

Case 2:
Another example ??????, it can be replaced as <<<>>> with length 6.

My program:

public static int process(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '?') {
c = '<';
}
sb.append(c);
}
int max = 0;
int open = 0;
int close = 0;
char[] arr = sb.toString().toCharArray();
for (int i=0; i<arr.length; i++) {
char c = arr[i];
if (c == '<') {
open++;
} else {
int j=i;
for(; j<arr.length && arr[j] == '>'; j++) {
close++;
int curr = Math.min(open, close);
max = Math.max(curr, max);
}
open = 0;
close = 0;
i = j;
}
}
int curr = Math.min(open, close);
max = Math.max(curr, max);
return max*2;
}

My program works for case 1 and fails for case 2 as I am always replacing ? with < symbols. what is the correct approach to solve this problem.

Constraints:

Length of string can be from 1 to 200,000

Here is a linear algorithm. It has 3 variables start, mid, and end. All start at the beginning of the string, at each step at least one advances, and at some point we'll be sure to find any symmetric pattern that can be made which is < until mid and then > afterwards.

Note, I'm using the idiosyncratic definition of "symmetric" in the OP. Namely, "first half letters are < and last half letters are >". This definition is NOT the same as a palindrome. So, for instance, <<><<>><>> would NOT be counted as symmetric.

def longest_symmetric (string):
start = mid = last_gt = end = 0
best = 0
while start < len(string):
#print(start, mid, last_gt, end)
current = min(mid - start, end - mid)
if best < current:
best = current
if end - mid == current and end < len(string):
if string[end] == '?':
end += 1
elif string[end] == '>':
end += 1
last_gt = end
else:
end += 1
mid = end
start = max(start, last_gt)
elif mid < len(string) and string[mid] == '?':
mid += 1
elif start < mid:
start += 1
else:
start = max(start, last_gt)
mid = mid + 1
end = max(mid, end)
return 2*best
for s in ('?????', '??????', '<><??>>', '<<?'):
print(s, longest_symmetric(s))

You did not specify the size of the input Strings, and since premature optimization is the root of all evil, I would start with a brute force approach.

I would put the case of calculating the result for a "string without the letter ?" to a seperate method. This can be used as a recursion starting point.
Then, given a String that includes the letter ?, I would simply replace it with < and call itself recursively, then replace it with > and call itself recursively, compare the results and see which is better.

Note, that this will solve the problem, but increases exponentially in runtime as well as in memory with the number of ? letters in the given input String. If that's an issue, I hope you can take this idea as a baseline and optimize from there.

Edit:
200k is definitely too much for exponential growth. With this in mind, let me point you to Manacher's algorithm

It has linear runtime and you might be able to adjust it to your problem setting by letting count ? as both < or >, when determining the longest palindrome around a certain center point.

Below is an algorithm that I came up with; I'm not too sure if it's even correct, but if it is, it runs in the required constraints.

Basically, we uses dynamic programming to calculate the Longest Symmetric Substring (LSS) of the input S from the current index, using the result from its right neighbor. I believe there are only a few states that we have to worry about, for any arbitrary index i:

1. If S[i] is a > then we can't build a symmetric substring from i.
2. Inspect one past the end of the LSS from i+1. If it's a > or ? we can make a longer LSS.
3. Otherwise, check if we can maintain the length of the neighboring LSS. We do some preprocessing and leverage the symmetry of what's considered a symmetric substring to do this quickly.
4. If we can't maintain the length of the neighbor, then we can't have a LSS starting from index i. (This is the part I'm not certain about)

Anyhow, below is an implementation of the above algorithm along with some tests in Python(3+). It passes the small test cases I've come up with, but this is certainly not exhaustive and I'm not sure if the algorithm is even correct.

def solve(S):
"""
LSS = longest symmetric substring
Returns (length of LSS, start index of LSS)
"""
N = len(S)
next_opens, closest_idx = [-1] * N, -1  # next_opens[i] = closest '(' to the left of i, inclusive
all_qs = set()                          # index of all '?'
for i, c in enumerate(S):
if c == '<':
closest_idx = i
elif c == '?':
all_qs.add(i)
next_opens[i] = closest_idx
res, F, best_idx = 0, [0] * N, -1      # F[i] = length of LSS starting from i, including it
for i in range(N - 2, -1, -1):
if S[i] == '>':                    # do not bother
F[i] = 0
continue
nb_len = F[i + 1]
if i+nb_len+1 < N and (S[i+nb_len+1] == '?' or S[i+nb_len+1] == '>'): # leverage symmetry of neighbor to extend
F[i] = nb_len + 2              # +2 bc of index i and character to right
if F[i] > res:                 # update result
res = F[i]
best_idx = i
elif (S[i+nb_len-1] == '?' or S[i+nb_len-1] == '>'): # can be nb length
n_open = nb_len//2             # how many '(' / '?' in the first half
last_open_idx = i + n_open - 1
if next_opens[i+nb_len-1] == last_open_idx or last_open_idx in all_qs:
F[i] = nb_len
else:                          # pretty sure if we can't do at least nb_len, it's 0
F[i] = 0
else:                              # definitely 0
F[i] = 0
return res, best_idx
def print_sol(S, best_len, sub_idx):
print("--------")
print(f"Input: {S}")
print(f"Answer: {best_len}")
if best_len:
print(f"Substring: {S[sub_idx:sub_idx+best_len]} starting at index {sub_idx}")
else:
print("No symmetric substring found")
return
def main():
for S in [
"<><??>>",
"<>?<??>>",
"<><<??>>",
"<>",
"<<<>>>",
"??????",
"?????",
"?",
"><",
">",
"<"
"<<<???<???????>>>>",
"<><>?????><??>",
"??????>>"
]:
res, sub_idx = solve(S)
print_sol(S, res, sub_idx)
return 0
if __name__ == "__main__":
main()

And below is some sample output of the above:

--------
Input: <><??>>
Answer: 4
Substring: ??>> starting at index 3
--------
Input: <>?<??>>
Answer: 6
Substring: ?<??>> starting at index 2
--------
Input: <><<??>>
Answer: 6
Substring: <<??>> starting at index 2
--------
Input: <>
Answer: 2
Substring: <> starting at index 0
--------
Input: <<<>>>
Answer: 6
Substring: <<<>>> starting at index 0
--------
Input: ??????
Answer: 6
Substring: ?????? starting at index 0
--------
Input: ?????
Answer: 4
Substring: ???? starting at index 1
--------
Input: ?
Answer: 0
No symmetric substring found
--------
Input: ><
Answer: 0
No symmetric substring found
--------
Input: >
Answer: 0
No symmetric substring found
--------
Input: <<<<???<???????>>>>
Answer: 18
Substring: <<<???<???????>>>> starting at index 1
--------
Input: <><>?????><??>
Answer: 6
Substring: ?????> starting at index 4
--------
Input: ??????>>
Answer: 8
Substring: ??????>> starting at index 0

I'm thinking about something like:

String s = "<><>?????><??>";

int len = s.length();

if (len < 2) {
   return 0;
}

int[] left = new int[len - 1];
int[] right = new int[len - 1];

left[0] = s.charAt(0) != '>' ? 1 : 0;
for (int i = 1; i < len - 1; i++) {
    left[i] = s.charAt(i) != '>' ? left[i - 1] + 1 : 0;
}

right[len - 2] = s.charAt(len - 1) != '<' ? 1 : 0;
for (int i = len - 3; i >= 0; i--) {
    right[i] = s.charAt(i + 1) != '<' ? right[i + 1] + 1 : 0;
}

int max = 0;
for (int i = 0; i < len - 1; i++) {
    max = Math.max(max, 2 * Math.min(left[i], right[i]));
}

return max;

i.e. for each position between symbols we count the continuous length of < and ? to the left and continuous length of > and ? to the right.

public class LongestSymmetricInString {
public static List<String> generateCombinations(String input) {
List<String> l = new ArrayList<String>();
char[] chars = input.toCharArray();
generateCombinationsHelper(chars, 0, l);
return l;
}
private static List<String> generateCombinationsHelper(char[] chars, int index, List<String> l) {
if (index == chars.length) {
l.add(new String(chars));
System.out.println(chars);
return l;
}
if (chars[index] == '?') {
chars[index] = '<';
generateCombinationsHelper(chars, index + 1, l);
chars[index] = '>';
generateCombinationsHelper(chars, index + 1, l);
chars[index] = '?'; // Reset the character back to '?' for backtracking
} else {
generateCombinationsHelper(chars, index + 1, l);
}
return l;
}
public static boolean isSymmetric(String str) {
int j = str.length();
if(j%2 != 0) return false;
if(!str.startsWith("<")) return false;
for(int i=0;i<str.length()/2;i++) {
if(str.charAt(i) != '<') return false;
if(str.charAt(str.length()-1-i) != '>') return false;
}
return true;
}
public static void main(String[] args) {
//  String input = "<><??>>";
//   String input = "??????";
String input = "<<?";
int max = 0;
List<String> l = generateCombinations(input);
System.out.println("**************");
for(int i=0;i<l.size();i++){
System.out.println(l.get(i).toString());
}
for(String li : l) {
for(int i=0; i<li.length();i++){
for(int j=i+1; j<li.length();j++){
if(isSymmetric(li.substring(i,j+1)) & max < li.substring(i,j+1).length()) {
max = li.substring(i,j+1).length();
System.out.println("##"+li.substring(i,j+1)+"");
}
}
}
}
System.out.println(max);
}
}

I hope helps, is JS

function findLongestSymmetricSubstring(S) {
let longestLength = 0;
// Iterate over all possible substrings of S
for (let i = 0; i < S.length; i++) {
for (let j = i + 1; j <= S.length; j++) {
let substring = S.substring(i, j);
// Check if the substring is symmetric
if (isSymmetric(substring)) {
let length = j - i;
longestLength = Math.max(longestLength, length);
}
}
}
return longestLength;
}
function isSymmetric(substring) {
let halfLength = substring.length / 2;
// Iterate through the first half of the substring
for (let i = 0; i < halfLength; i++) {
// Check if the corresponding characters in the second half are in the correct format ("<" or ">")
// or if they are "?" characters
if (
(substring[i] !== "<" && substring[i] !== "?") ||
(substring[i + halfLength] !== ">" && substring[i + halfLength] !== "?")
) {
return false;
}
}
return true;
}
console.log(findLongestSymmetricSubstring("<><??>>"));  // Output: 4
console.log(findLongestSymmetricSubstring("??????"));  // Output: 6

The code in Java

public class LongestSymmetricInStringWithoutGeneration {
public int isSymmetric(String S) {
int max = 0;
for(int i = 0; i < S.length(); i ++){
for (int j = i +1; j <= S.length(); j++){
String t = S.substring(i,j);
if(t.length()%2 == 0){
int k = 0, l = t.length()-1;
boolean isSym = true;
while(k < l && isSym){
if(!(t.charAt(k) == '<' || t.charAt(k) == '?') && (t.charAt(l) == '>' || t.charAt(l) == '?')){
isSym = false;
}
k++;
l--;
}
if(isSym){
max = Math.max(max,t.length());
}
}
}
}
return max;
}
}

Lets have some kind of tasks which expects in this manner.
We have a string made of an even number of characters ("<" and/or ">") which is called symmetric if all characters in its first half are "<" and all characters in its second half are ">". Examples of symmetric strings are: "" (empty string), "<>", "<<>>", "<<<>>>", etc.

function solution(S);
that, given a string S made of N characters ("<", ">" and/or "?")", returns the length of the longest symmetric substring that can be obtained after replacing question marks with "<" or ">" characters.
Examples:
1. For S = "<><??>>", after replacing all question marks with "<", the string "<><<<>>" is obtained. Its longest symmetric substring is "<<>>", so the function should return 4.
2. For S = "??????", the optimal option is to replace the first three question marks with "<" and the next three question marks with ">", thus obtaining the string "<<<>>>". The function should return 6.
3. For S = "<<?", the function should return 2.
HERE IS THE SOLUTION FOR THIS PROBLEM :
function solution(S) {
let left = 0;
let right = S.length - 1;
let count = 0;
let result = 0;
while (left < right) {
if (S[left] === S[right]) {
count += S[left] === '?' ? 1 : 2;
} else if (S[left] !== '?' && S[right] !== '?' && S[left] !== S[right]) {
count = 0;
} else {
count += 2;
}
result = Math.max(result, count);
left++;
right--;
}
return result;
}
// Examples
console.log(solution("<><??>>")); // Output: 4
console.log(solution("??????")); // Output: 6
console.log(solution("<<?")); // Output: 2