Entering edit mode

Click here to Practice

Submit Problem to OJ

Given a string *s*, repeat this operation zero or more times to create the lexicographically smallest string possible.

- Select two characters that exist in the string,
*c1*and*c2*. - Replace all occurrences of
*c1*with*c2*and all occurrences of*c2*with*c1*.

Note: For two strings x and y of length n, x is lexicographically smaller than y if the first non-matching character in x is less than the character at that position in y.

**Example**

*s* = 'bbcacad'

- Select
*c1*= 'b' and*c2*= 'a', after swapping occurrences s = 'aacbcbd' - Select
*c1*= 'b' and*c2*= 'c', after swapping occurrences of*c1*and*c2*we get s = 'aabcbcd'

It can be prove that this is the lexicographically smallest string *s* can be converted to. Return 'aabcbcd'.

**Function Description**

Complete the function *getString* in the editor below.

*getString* has the following parameter: *string s*: the string to process

**Returns**

*string*: the lexicographically smallest string s can be changed to

**Constraints**

- 1 <= |s| <= 10^5
- The string s contains lowercase English letters

**Sample Input for Custom Testing**

bdea

**Sample Output**

abde

Click here to Practice

Submit Problem to OJ

An array of n integers, arr[n] can be partitioned into any number of contiguous subsegments. Every element must present in exactly 1 partition.

After participating, and without changing the order of partitions, sort each partition in non-descending order. Concatenate the sorted partitions and compare the resulting array to the original array, sorted non-descending, if the two match, the set of partitions is valid.

Find the maximum number of contiguous subsegments in which the array arr can be partitioned such that the set of partitions is valid.

**Example**

n = 6

arr = [2, 5, 1, 9, 7, 6]

The array can be divided into 2 contiguous subsegments:

Subsegments -> [2, 5, 1], [9, 7, 6]

Sorted subsegments -> [1, 2 ,5], [6, 7, 9]

Final array -> [1, 2, 5, 6, 7, 9]

As the final arr is sorted, 2 is a possible answer.

The array can be divided into 3 contiguous subsegments:

Subsegments -> [2, 5, 1], [9, 7], [6]

Sorted subsegments -> [1, 2 ,5], [7, 9], [6]

Final array -> [1, 2, 5, 7, 9, 6]

As the combined arr is not sorted, 3 can't be possible.

Any higher number of subsegments will fail as well. The answer is 2.

**Function Description**

Complete the function *findMaxSubsegmentsCount* in the editor below:

*findMaxSubsegmentsCount* has the following parameter(s):

*int arr[n]*: the array of integers to partition

**Returns**

*int*: the maximum number of contiguous subsegments in a valid set of partitions

**Constraints:**

- 1 <= n <= 10^5
- 1 <=
*arr[i]*<= 10^5

**Sample Case 0**

```
STDIN FUNCTION
4 - n = 4
2 - arr = [2, 10, 5, 9]
10
5
9
```

**Sample Output**

```
2
```

**Explanation**

Subsegments after partitions -> [2], [10, 5, 9]

Sorted subsegments -> [2], [5, 9, 10]

Final array -> [2, 5, 9, 10] (Sorted)

Entering edit mode

Split the array into maximum number of subsegments such that if we sort every subsegment individually and concatenate them in the original order, we get the non decreasing sorted version of the original array.

As we can see, we can create a partition wherever max(prefix array) <= min(suffix array), as if this condition is violated, the array won't become sorted.

Hence, we will create the partition wherever we find such a condition to hold true, for the maximum number of partitions.

```
int solve(vector<int> arr) {
int n=arr.size();
vector<int> mx(n,0);
mx[0]=arr[0];
for(int i = 1;i < n;i++)
mx[i]=max(mx[i-1],arr[i]);
vector<int> mn(n,0);
mn[n-1]=arr[n-1];
for(int i = n-2;i >= 0;i--)
mn[i]=min(mn[i+1],arr[i]);
int ans=0;
for(int i = 0;i < n-1;i++)
{
if(mx[i]<=mn[i+1])
ans++;
}
return ans+1; // +1 for last partition
}
```

Time Complexity : `O(N)`

, where N is the size of the input array.

Entering edit mode

- For a given string in one operation, you can swap all occurrences of two characters. Perform any number of operations to create the lexicographically smallest string possible.

- Since we can perform the operation any number of terms, we will store the first occurrence of each character and, in the increasing order of indices, map it with the respective smallest character. For example, the first character will be matched with the smallest character; the next new character will be matched with the second smallest character, and so on.
- For example,
`s = "bbcacad”`

• Select`c1=b`

and`c2=a`

after swapping occurrences`s = “aacbcbd"`

• Select `c1=c`

and `c2=b`

after swapping occurrences of c1 and c2 we get `s = “aabcbcd”`

Time Complexity: `O(NlogN), N`

is the size of string.

Loading Similar Posts