Scaler Topics Fortnightly Contest - 28 Editorial
DSA Fortnightly - 28 Editorial
This article is part of the Scaler Topics Fortnightly Contest - 28
Lucky Number
In this realm, A holds the status of a lucky number. Given a string B with a size exceeding A, your task is to eliminate precisely A characters and ascertain whether the resulting string (with its characters arranged in any manner) is a palindrome or not.
Problem Constraints
Input Format
- The first argument is integer A.
- The second argument is string of characters B.
Output Format
- Return 1 if after removing exactly A characters from B , it becomes a palindrome else return 0.
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: In "abb" we can remove B[0], hence the string becomes "bb" which is a palindrome.
Explanation 2: "ab" is not a palindrome.
Hint
- Think of a greedy approach to apply.
Complete Solution
Palindromifier
Given a string A of length N, containing only lowercase letters from the English alphabet. We would like to turn string A into a palindrome by applying two types of operations to the string-
The first operation allows you to choose i (2 ≤ i ≤ n−1) and to append the substring A2A3…Ai (i-1 characters) reversed to the front of A.
The second operation allows you to choose i (2 ≤ i ≤ n−1) and to append the substring Ai+1Ai+2…AN-1 (n-i characters) reversed to the end of A.
Find if the string can be turned into a palindrome in at most 1 move. Return 1 if it can be done, else print 0.
Problem Constraints
Input Format
- The first argument is a string A.
Output Format
- Return an integer, 1 or 0.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: As this string is already a palindrome, we don’t need to perform any operation.
Explanation 2: There is no possible move to convert this string into a palindrome in the next move.
Hint
- Simple brute force can be enough to solve this problem.
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreComplete Solution
Height of wall
Consider a wall represented by an array A, consisting of N segments horizontally. Each element Ai in the array signifies the height of the wall at the i-th segment. As the new constructor of the wall, your task is to maximize the overall height of the wall while adhering to a specific condition. The height of the wall is defined as the maximum number of vertically stacked blocks within any given N segments arranged horizontally. You can increase the height of a particular segment by adding one more block on top of it only if the height of the immediately consecutive segment is greater than or equal to the current one. Determine the maximum height achievable for the constructed wall.
Assume that you only have B additional blocks, hence you can do the above operations no more than B times.
Problem Constraints
Input Format
- The first argument is array of integers A.
- The second argument is integer B.
Output Format
- Return maximum height of wall possible.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: In the initial test case, one potential optimal sequence of operations could be: [1, 3, 3] → [2, 3, 3] → [2, 4, 3] → [3, 4, 3] → [4, 4, 3].
Explanation 2: [3, 5] → [4, 5] → [5, 5] → [6, 5].
Turn Learning into Career Growth
Hint
- Use binary search to reach the answer.
- Look at the constraints carefully and try to analyse code by analysing complexity.
Complete Solution
Subarray Size-OR
Given an array A of integers of size N, find the number of non-empty subarrays with their size equal to OR sum.
Problem Constraints
Input Format
- The first argument is an integer array A.
Output Format
- Return an integer, the number of subarrays.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1:
There are a total of 6 subarrays - [1], [0], [1], [1, 0], [0, 1], [1, 0, 1]. Only the 2 subarrays - [1] and [1] have the size = OR sum, i.e., 1.
Explanation 2:
As all the subarrays have the OR as 0, no OR can match the size. So, the answer is 0.
Hint
- How many times can an OR sum change from a particular fixed point? How can you optimize the search?
