Solution 3 for Scaler Topics Fortnightly Contest - 9

This article is part of the Scaler Topics Fortnightly Contest - 9

Transform Your Career

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

Solution Approach

• Let's build the string character by character.
• While adding characters to end of the string we only care about the last character and length of the continuous occurrence of this character in the end of the string.
• Let the last character of the string be C and it's occurence in the end be CNT, if CNT is less than B then we can add C again to our string else we need to choose a different character.
• Doing the above process by brute force is not optimal, so here we can use DP.
• Let DP[i][j][k] denote the number of strings of length i, last character j and count of j in end of the string is k.

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation