What is the time and space complexity of Permutation in String?

Time complexity: O(n). Space complexity: O(1).

Permutation in String

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Permutation in String

Approach

Build a frequency map for s1. Slide a fixed-size window of length s1.length over s2, maintaining a frequency map for the current window. At each position, compare the two frequency maps. If they match, s2 contains a permutation of s1.

Complexity Analysis

Time: O(n)
Space: O(1)

Pattern

Sliding Window (Fixed Size + Frequency)

Why It Works

Two strings are permutations of each other if and only if they have identical character frequencies. By maintaining a sliding frequency map, we check every possible substring of the correct length in O(1) amortized time per position.

Updated Mar 2026