8 weeks ago

Rohit • 210

Question 1

Characters Swap

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

1. Select two characters that exist in the string, c1 and c2.
2. 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

Question 2

Subsegment Sort

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)

3 months ago

HARDIK • 40

Question 2

Description

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.

Approach

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.

C++ Code

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.

3 hours ago

Akash 150

Question 1: Character Swap

Overview

• 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.

Approach

• 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”

Complexity

Time Complexity: O(NlogN), N is the size of string.

5 weeks ago

江柏毅 • 10

Hello, I'm the student of Taiwan National Ocean University.

I get Wrong Answer when im trying to solve the problem 1(testcase 2)

Could I bother you to send me the testcase 2?

thank you <3

 mail: ben880308@gmail.com