2.0 years ago

namansingh.singh9 • 30

<h2>About Coding Round</h2>

• Languages allowed - c#,c++,c,java
• Multiple sets of 3 questions. Below discussed is from one such set.
• Platform - cocubes
• Time -70 min only 3 coding question
• we were allowed only to check some test cases only 4-5.
</ul> <hr> <h2>Coding Round</h2> <h3>Problem 1 (3 marks)</h3> Given a list of numbers and a digit k, find which number has the largest occurrence of k digit. Return that number<br> <h3>Problem 2 (3 marks)</h3> Given coins of rs 1,2,5,10,100,20,2000 and an amount find fewest no of coins to make the sum<br>
Click here to Practice
Submit Problem to OJ

<h3>Problem 3 (5 marks)</h3> Minimum no of cuts to make all substring palindromic.<br> <pre> Example Input: geek <br> Example Output: 2 <br> Explanation: g ee k (2 cuts required)<br></pre>

11 months ago

Ujjwal Srivastava 320

Bengaluru

Question 3 Palindrome Partitioning

Overview

• Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome.
• Determine the fewest cuts needed for a palindrome partitioning of a given string.
• If a string of length n contains all different characters, then minimum n-1 cuts are needed.

Solution

• A solution is to initialize an array cut[n] which will denote the minimum cuts required till index i.
• Also initialize a 2-d array named palindrome with false which denotes if the string from index i to j is a palindrome or not.
• Now apply 2 for loops, the first loop would be for i from 0 to n-1 and the second loop would be for j which would be from 0 to i.
• Now we need to find the minimum cut required up to index i.
• Initialize a variable minCut=i, for each index i which is the maximum value for the current prefix.
• To calculate this for index i, we would consider all index j from 0 to i and see if s[j..i] is a palindrome, if so assign minCut `as min( minCut, cut[j-1]+1).`
• In cut[j-1]+1 , 1 stands for 1 cut in between j-1 and j and cut[j-1] stands for minimum cut up to j-1.
• Assign cut[i] = minCut.
• At last print the answer as cut[n-1].
• Time Complexity : O(n*n)

Code

ll n;
cin >> n;
string s;
cin >> s;
ll cut[n];             // declare an array cut denoting minimum cuts required till index i
bool palindrome[n][n]; // initialize a 2-d array named palindrome with false which denotes if index i to j is a palindrome or not
memset(palindrome, false, sizeof(palindrome));
for (ll i = 0; i < n; i++)
{
    ll minCut = i; // initialize a variable minCut as the length of current prefix-1 which is the maximum value
    for (ll j = 0; j <= i; j++)
    {
        if (s[i] == s[j] && (i - j < 2 || palindrome[j + 1][i - 1])) // now we know the value of cut[j] for all j less than i
        {
            palindrome[j][i] = true;                             // now if the string from j to i is a palindrome
            minCut = min(minCut, j == 0 ? 0 : (cut[j - 1] + 1)); // In cut[j-1]+1, 1 stands for 1 cut in between j-1 and j  and cut[j-1] stands for minimum cut upto j-1
        }
    }
    cut[i] = minCut; // assign minCut to cut[i] which is minimum cut required upto index i
}
cout << cut[n - 1] << endl; // print the required answer