Question 3: Minimum Disorder Events

Problem Statement

A system receives two separate log streams, logStreamA and logStreamB . These logs must be merged into a single output sequence while preserving each stream's relative order of log entries. For instance, if logStreamA = "abc" and logStreamB = "def", valid merged outputs include "abcdef" and "defabc". Outputs such as "acdbef" or "abcdfe" are invalid because they break the original ordering of entries within at least one stream. After merging, the system evaluates the output based on disorder events . A disorder event occurs when an entry that appears earlier in the merged sequence has a higher lexicographical value than an entry appearing later. Formally, in a merged sequence mergedLogs , a disorder event is a pair of indices (i, j) such that i < j and mergedLogs[i] > mergedLogs[j] . The task is to determine the minimum number of disorder events that can be achieved by optimally merging logStreamA and logStreamB . Example logStreamA = "ye" and logStreamB = "m": Possible merged out