Permutation in String

Animated walkthrough

Step through the algorithm visually — use Play or the step buttons (inspired by AlgoMaster / visualgo).

Step 1 / 1

Walmart Labs interview context: Permutation in String is a Medium Sliding Window problem — Maintain a window [L, R] and update counts as you expand or contract.

Use the animation above to step through each move before writing code.

Pattern: Sliding Window

Read from stdin, write to stdout. Classic interview problem #567.

Problem

Permutation in String — Walmart Labs interview prep · Sliding Window

Classic interview problem #567.

Input (stdin)

Line 1: s1\nLine 2: s2

Output (stdout)

true if permutation of s1 in s2

Your program must read from stdin and write the answer to stdout (no extra debug text).

Examples

Sample

Input

ab
eidbaooo

Output

true

Hints

Input format: Line 1: s1\nLine 2: s2
DSA Interview 150 — Sliding Window
Problem #567
Frequently asked at Walmart Labs
Sliding Window

Your solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static int[] Ria(string line = null)
    {
        line ??= Console.ReadLine();
        if (string.IsNullOrWhiteSpace(line)) return Array.Empty<int>();
        return line.Trim().Split(new[] { ' ', ',', '\t' }, StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse).ToArray();
    }
    static string[] Rsa()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = new string[n];
        for (int i = 0; i < n; i++) arr[i] = Console.ReadLine();
        return arr;
    }
    static void W(params object[] parts) => Console.WriteLine(string.Join(" ", parts));
    static void Wb(bool v) => Console.WriteLine(v ? "true" : "false");
    static void Wi(int v) => Console.WriteLine(v);
    static void Ws(string v) => Console.WriteLine(v);

static void Main()
    {
        // Read from stdin (see problem statement for format)
        // Line 1: s1\nLine 2: s2

}
}

Ready — edit the code above and click Run or Submit.

Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static int[] Ria(string line = null)
    {
        line ??= Console.ReadLine();
        if (string.IsNullOrWhiteSpace(line)) return Array.Empty<int>();
        return line.Trim().Split(new[] { ' ', ',', '\t' }, StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse).ToArray();
    }
    static string[] Rsa()
    {
        int n = int.Parse(Console.ReadLine());
        var arr = new string[n];
        for (int i = 0; i < n; i++) arr[i] = Console.ReadLine();
        return arr;
    }
    static void W(params object[] parts) => Console.WriteLine(string.Join(" ", parts));
    static void Wb(bool v) => Console.WriteLine(v ? "true" : "false");
    static void Wi(int v) => Console.WriteLine(v);
    static void Ws(string v) => Console.WriteLine(v);

    static void Main()
    {
string s1 = Console.ReadLine();
string s2 = Console.ReadLine();
var need = new int[26], have = new int[26];
foreach (var c in s1) need[c - 'a']++;
int matches = 0;
for (int i = 0; i < 26; i++) if (need[i] == 0) matches++;
bool found = false;
for (int i = 0; i < s2.Length; i++) {
    int idx = s2[i] - 'a';
    have[idx]++;
    if (have[idx] == need[idx]) matches++;
    else if (have[idx] == need[idx] + 1) matches--;
    if (i >= s1.Length) {
        int outIdx = s2[i - s1.Length] - 'a';
        have[outIdx]--;
        if (have[outIdx] == need[outIdx]) matches++;
        else if (have[outIdx] == need[outIdx] - 1) matches--;
    }
    if (matches == 26) { found = true; break; }
}
Wb(found);
    }
}

Try solving on your own first, then reveal the official answer.

Animated walkthrough

Problem

Examples

Your solution

Solution

Discussion