aboutsummaryrefslogtreecommitdiff
path: root/permutation_in_string.c
blob: b6d087841fdd9fbe29905925e7a7410b979ba0ee (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 567. Permutation in String
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * given two strings 's1 s2' return true if 's2' contains a permutation of 's1'
 * or false otherwise. in other words, return true if one of 's1's permutations
 * is in the substring of 's2'
 */

bool checkInclusion(char *s1, char *s2) {
  int len1 = strlen(s1), len2 = strlen(s2);
  if (len1 > len2)
    return false;
  int freq1[128] = {0}, freq2[128] = {0};
  for (int i = 0; i < len1; i++) {
    freq1[s1[i]]++;
    freq2[s2[i]]++;
  }
  if (memcmp(freq1, freq2, sizeof(freq1)) == 0)
    return true;
  for (int i = len1; i < len2; i++) {
    --freq2[s2[i - len1]];
    ++freq2[s2[i]];
    if (memcmp(freq1, freq2, sizeof(freq1)) == 0)
      return true;
  }
  return false;
}

int main() {
  char s[] = "ab", s1[] = "eidbaooo", s2[] = "eidboaoo";
  printf("%d\n", checkInclusion(s, s1)); // expect: 1
  printf("%d\n", checkInclusion(s, s2)); // expect: 1
}