Solution 4 for Scaler Topics Fortnightly Contest - 2

This article is part of the Scaler Topics Fortnightly Contest - 2.

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

• You can keep a 2D dp, where first parameter will be the index of string and second parameter will be whether you have reversed this string or not. Initialize your dp to a large number.
• Let Br be the array where all the strings are reversed.
• Now for each index i check these four cases : if B[i-1] <= B[i] , then update your dp[i][0] to min of dp[i][0], dp[i-1][0]. if Br[i-1] <= B[i] , then update your dp[i][0] to min of dp[i][0], dp[i-1][1]. if B[i-1] <= Br[i] , then update your dp[i][1] to min of dp[i][1], dp[i-1][0]. if Br[i-1] <= Br[i] , then update your dp[i][1] to min of dp[i][1], dp[i-1][1]. And your answer will be minimum of dp[n][0] and dp[n][1].
• If the answer is equal to or greater thant the large number to initialized your dp with. Then it means you cannot sort your array.

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation