Monday, November 28, 2022
HomeSoftware DevelopmentDiscover Array shaped by reversing Prefix every time given character is discovered

Discover Array shaped by reversing Prefix every time given character is discovered


Given an array arr[] of size N consisting of uppercase English letters solely and a letter ch. the duty is to seek out the ultimate array that can type by reversing the prefix every time the letter ch is discovered within the array.

Examples:

Enter: arr[] = {‘A’, ‘B’, ‘X’, ‘C’, ‘D’, ‘X’, ‘F’}, ch= ‘X’
Output: D C X A B X F 
Rationalization
First encounter of ‘X’ at index 2, Preliminary subarray = A, B, Closing subarray = B, A, X.
Second encounter of ‘X’ at index 5, Preliminary subarray = B, A, X, C, D 
Closing subarray = D, C, X, A, B, X(added).
Closing subarray after traversing, = D, C, X, A, B, X, F

Enter: arr[] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}, ch = ‘F’
Output: A B C D E

 

Strategy: The concept to resolve the issue is as follows:

If every portion between two occurrences of ch (or the ends of the array) is taken into account a section, then the prefix reversals of the string could be visualised as appending the characters of a section alternatively on the beginning and the ending of string and preserve increasing outwards. 

  • So concept is to push the ingredient of the array into again of a listing until ch happens for first time. 
  • When first ch happens, push the weather, together with ch, to the entrance of the checklist until the following ch happens. Once more if ch happens push the weather to the again of the checklist, together with ch
  • So, the conclusion is that every time ch happens, it’s a must to change the course of pushing the weather.

Be aware:  If there may be odd variety of Okay within the array, it’s essential reverse the checklist as we begin pushing ingredient from again.

Comply with The steps given under

  •  Create a listing named li to retailer the weather
  •  Create a variable named discovered to verify which facet it’s a must to add the weather from
  •  If ch happens flip the worth of discovered from 1 to 0 or 0 to 1.
    • If discovered is the same as 1 add the weather to the entrance
    • Else add the weather to the again
  •  If ch happens odd variety of occasions reverse the checklist and print, else print it merely 

Beneath is the implementation of the above method:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

  

checklist<char> findFinalString(char* arr, int n, char ch)

{

    checklist<char> li;

    bool discovered = 0;

  

    for (int i = 0; i < n; i++) {

  

        

        if (arr[i] == ch)

            discovered = !discovered;

  

        

        if (discovered)

            li.push_front(arr[i]);

  

        

        else

            li.push_back(arr[i]);

    }

  

    

    if (discovered == 1)

        li.reverse();

  

    

    return li;

}

  

int important()

{

    char arr[] = { 'A', 'B', 'X', 'C', 'D', 'X', 'F' };

    char ch = 'X';

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    checklist<char> ans = findFinalString(arr, N, ch);

    for (auto itr = ans.start();

         itr != ans.finish(); itr++)

        cout << *itr << " ";

  

    return 0;

}

Time Complexity: O(N)
Auxiliary Area: O(N)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments