Show problems as
Classic problem #1208MediumStringBinary SearchSliding WindowPrefix Sum

Get Equal Substrings Within Budget

Real-world version: Longest Stretch Retinted Within Budget
Tracked in this browser only
Read Get Equal Substrings Within Budget on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A ribbon press holds two rolls of the same length. Every position on a roll carries one shade, written as a lowercase letter, so panel and pattern are strings of equal length and panel[i], pattern[i] are the shades sitting at position i on the two rolls.

Give each letter its place in the alphabet, with "a" worth 0 and "z" worth 25. Retinting one position of panel so that it carries the shade pattern has at that position costs the absolute difference of the two values in units of ink, so a position that already carries the right shade costs nothing.

You hold budget units of ink. Pick one contiguous stretch of positions and retint every position inside it so the stretch matches pattern there, spending at most budget units in total across the stretch. Positions outside the stretch are left alone.

Return the number of positions in the longest stretch you can finish. An empty stretch is always allowed and has length 0.

Examples

Example 1

Input
panel = "dqgh", pattern = "cqfi", budget = 2
Output
3

Retinting positions 0, 1 and 2 costs 1 + 0 + 1 = 2 units of ink, which the budget covers, and that stretch holds 3 positions.

Example 2

Input
panel = "wq", pattern = "aa", budget = 0
Output
0

Position 0 needs 22 units and position 1 needs 16, so with no ink at all only the empty stretch is affordable.

Example 3

Input
panel = "cbbb", pattern = "aaaa", budget = 3
Output
3

The four positions need 2, 1, 1 and 1 units. Positions 1, 2 and 3 together need 3 units, which the budget covers, and that stretch holds 3 positions.

Constraints

  • 1 <= panel.length <= 10^5
  • pattern.length == panel.length
  • 0 <= budget <= 10^6
  • panel and pattern hold lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_retinted_stretch(panel: str, pattern: str, budget: int) -> int:
Java
public int longestRetintedStretch(String panel, String pattern, int budget)

More on the same topics