Let's iterate through the given array and store the length of the current increasing subarray in the variable $$$curLen$$$. If the current element is more than the previous we need to increase $$$curLen$$$ by one. Otherwise, the current number is a start of a new increasing subarray, so we need to restart $$$curLen$$$ with $$$1$$$. We keep track of the maximum after considering every number.

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = list(map(int, input().split()))

max_len = 1
cur_len = 1

for idx in range(1, n):
    if a[idx - 1] >= a[idx]:
        cur_len = 0
    
    cur_len += 1
    max_len = max(max_len, cur_len)

print(max_len)
    

Let's suppose that when we calculate the collapse of two strings $$$a$$$ and $$$b$$$, we reverse the string a first, so that instead of checking and removing the last letters of $$$a$$$, we do this to the first letters of $$$a$$$. Then, $$$|C(a,b)|=|a|+|b|−2|LCP(a′,b)|$$$, where $$$LCP(a′,b)$$$ is the longest common prefix of $$$a′$$$ (the reversed version of $$$a$$$) and $$$b$$$.

Then the answer to the problem becomes $$$ 2n \sum_{i=1}^{n} |s_i| - 2 \sum_{i=1}^{n} \sum_{j=1}^{n} \text{LCP}(s_i, s_j) $$$.

We need some sort of data structure that allows us to store all strings $$$s_i$$$ and for every string $$$s_j$$$, calculate the total $$$LCP$$$ of it with all strings in the structure. There are many ways to implement it (hashing, suffix arrays, etc), but in our opinion, one of the most straightforward is using a trie.

Build a trie on all strings $$$s_i$$$. Then, for every vertex of the trie, calculate the number of strings $$$s_i$$$ that end in the subtree of that vertex (you can maintain it while building the trie: when you add a new string into it, increase this value by 1 on every vertex you go through).

If you want to find the LCP of two strings $$$s$$$ and $$$t$$$ using a trie, you can use the fact that it is equal to the number of vertices that are both on the path to $$$s$$$ and on the path to $$$t$$$ at the same time (except for the root vertex). This method can be expanded to querying the sum of LCP of a given string $$$s$$$ and all strings in the trie as follows: try to find $$$s$$$ in the trie. While searching for it, you will descend in the trie and go through vertices that represent prefixes of $$$s$$$. For every such prefix, you need the number of strings in the trie that have the same prefix — and it is equal to the number of strings ending in the subtree of the corresponding vertex (which we already calculated). Don't forget that you shouldn't consider the root, since the root represents the empty prefix.

class Trienode:
	def __init__(self):
    	self.child= {}
    	self.cnt = 0
    
   	 
class Trie:

	def __init__(self):
    	self.root=Trienode()
   	 
	def insert(self, word: str) -> None:
   	 
    	cur = self.root
   	 
    	for c in word:
        	ind=ord(c)-ord("a")

        	if ind  not in cur.child:
            	cur.child[ind]=Trienode()
        	cur=cur.child[ind]
        	cur.cnt += 1
   	 
   	 
	def search(self, word: str) -> int:
   	 
    	cur=self.root
    	tot = 0
    	for c in word:
        	ind=ord(c)-ord("a")
        	if ind not in cur.child:
            	return tot
        	cur=cur.child[ind]
        	tot += cur.cnt * 2

    	return tot

n = int(input())
s = [input() for i in range(n)]
trie = Trie()
for cur in s:
	trie.insert(cur)
total = sum([len(cur)*2*n for cur in s])
for cur in s:
	total -= trie.search(cur[::-1])
print(total)

To solve this problem efficiently, we can sort the given input array of word length in ascending order while keeping track of their original indices.It helps in generating the smallest possible lexicographical strings by starting with the shortest strings. Using a $$$Trie$$$ data structure, we efficiently generate unique binary strings for each length, which are not a prefix of other words. For each length, starting from the smallest, we can build a binary string by traversing the $$$Trie$$$. If a binary string of the required length cannot be uniquely formed (i.e., both possible extensions lead to existing valid prefixs), we will return $$$NO$$$. If successful, we can store the binary string and update the $$$Trie$$$ to reflect the newly added string. After forming a binary string, we have to backtrack to update the $$$is_end$$$ flags appropriately to ensure that we correctly mark nodes as end nodes when there are no further possible paths (all childrens are occupied).

Time Complexity: $$$O(NlogN + N * M)$$$ time. N is input array length and M denotes the maximum word length

Space Complexity: $$$O(N * M)$$$

class TrieNode:
    def __init__(self):
        self.ch = [None, None]
        self.is_end = False 

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, length):
        stack, trie = [], self.root 
        word = []
        # finding a unique word representation with the given length
        for i in range(length):
            stack.append(trie) 
            if trie.ch[0] is None or not trie.ch[0].is_end:
                if trie.ch[0] is None:
                    trie.ch[0] = TrieNode()
                trie = trie.ch[0]
                word.append('0')
            elif trie.ch[1] is None or not trie.ch[1].is_end:
                if trie.ch[1] is None:
                    trie.ch[1] = TrieNode()
                trie = trie.ch[1]
                word.append('1')
            else:
                return False
        trie.is_end = True

        # backtrcking to update the is_end of the nodes if they don't have unoccopied child for the word represetnation
        while stack and stack[-1].ch[1] and stack[-1].ch[1].is_end:
            prev = stack.pop()
            prev.is_end = True

        return ''.join(word)

def main():
    n = int(input())    
    nums = sorted(zip(map(int, input().split()), range(n)))
    trie = Trie()
    words = [''] * n
    for num, indx in nums:
        word = trie.insert(num)
        if not word:
            print('NO')
            return
        words[indx] = word

    print('YES')
    for word in words:
        print(word)

if __name__ == '__main__':
    main()

How can we find the best possible match for the XOR of some number from an array using a Trie?.

Can We use the same concept for prefix and suffix?

For this problem, we will use the Trie data structure. Let's start by calculating the prefix of the array. For $$$(0 \leq i \leq n)$$$, let $$$pref[0] = 0$$$. After calculating $$$prefix[i]$$$, we should add $$$prefix[i]$$$ to the Trie. Then, we can easily calculate the best possible match for the XOR of the new suffix that starts from $$$n$$$ and ends at $$$i + 1$$$. In this case, we are guaranteed that the prefix and suffix do not intersect.

import sys
   
class Node:
    def __init__(self):
        self.children = [None, None]

class Trie:
    def __init__(self, val):
        self.root = Node()
        self.bit_len = val

    def insert(self, num):
        cur = self.root
     
        for  i in range(self.bit_len, -1, -1):
            bit = 1 if num & (1 << i)else 0
            if cur.children[bit] is None:
                cur.children[bit] = Node()
            cur = cur.children[bit]
            
    def findMax(self, num):
        cur = self.root
        max_num = 0
        for  i in range(self.bit_len, -1, -1):
            bit = 1 if num & (1 << i) else 0
            if cur.children[1 - bit] is not None:
                max_num = max_num | (1 << i)
                cur = cur.children[1 - bit]
            else:
                cur = cur.children[bit]
        return max_num

n = int(sys.stdin.readline().strip())

nums = list(map(int, sys.stdin.readline().strip().split()))

trie = Trie(len(bin(max(nums))))

tot_pref = 0
nums = [0] + nums

for num in nums:
    tot_pref ^= num

cur_pref = 0
ans = 0

for  num in nums:
    cur_pref ^= num
    trie.insert(cur_pref)
    ans = max(ans, trie.findMax(cur_pref ^ tot_pref))

print(ans)