Show problems as
Classic problem #567MediumHash TableTwo PointersStringSliding Window

Permutation in String

Real-world version: Seed Row Packet Window
Tracked in this browser only
Read Permutation in String on LeetCode(opens in a new tab)

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

A seed catalogue codes every variety with a single lowercase letter. The string packet lists the seeds inside one packet, and the string row lists, in planting order, the seeds a gardener has already put in the ground along a long bed.

The gardener wants to know whether some unbroken stretch of the bed was planted from exactly one packet's worth of seed: a stretch qualifies when it holds the same varieties as packet in the same quantities, planted in whatever order. Return true if such a stretch exists in row, and false if none does.

Quantities count. A packet with two a seeds does not match a stretch holding one a and two b seeds, even though both draw on the same two varieties.

Examples

Example 1

Input
packet = "abc", row = "zzbca"
Output
true

The three seeds planted at positions 2 through 4 are one of each variety, matching the packet in a different order.

Example 2

Input
packet = "aab", row = "zabbz"
Output
false

Every three-seed stretch either includes a z or holds one a and two b seeds, while the packet holds two a and one b.

Example 3

Input
packet = "ba", row = "xxab"
Output
true

The qualifying stretch is the final pair of seeds, so the last stretch of the bed has to be examined too.

Constraints

  • 1 <= packet.length <= 10^4
  • 1 <= row.length <= 10^4
  • packet and row consist of lowercase English letters
  • packet may be longer than row, in which case no stretch can qualify

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 contains_packet_window(packet: str, row: str) -> bool:
Java
public boolean containsPacketWindow(String packet, String row)

More on the same topics