Posts tagged as “suffix”

花花酱 LeetCode 2256. Minimum Average Difference

By zxi on May 1, 2022

You are given a 0-indexed integer array nums of length n.

The average difference of the index i is the absolute difference between the average of the first i + 1 elements of nums and the average of the last n - i - 1 elements. Both averages should be rounded down to the nearest integer.

Return the index with the minimum average difference. If there are multiple such indices, return the smallest one.

Note:

The absolute difference of two numbers is the absolute value of their difference.
The average of n elements is the sum of the n elements divided (integer division) by n.
The average of 0 elements is considered to be 0.

Example 1:

Input: nums = [2,5,3,9,5,3]
Output: 3
Explanation:
- The average difference of index 0 is: |2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3.
- The average difference of index 1 is: |(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2.
- The average difference of index 2 is: |(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2.
- The average difference of index 3 is: |(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0.
- The average difference of index 4 is: |(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1.
- The average difference of index 5 is: |(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4.
The average difference of index 3 is the minimum average difference so return 3.

Example 2:

Input: nums = [0]
Output: 0
Explanation:
The only index is 0 so return 0.
The average difference of index 0 is: |0 / 1 - 0| = |0 - 0| = 0.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Solution: Prefix / Suffix Sum

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

C++

// Author: Huahua

class Solution {

public:

int minimumAverageDifference(vector<int>& nums) {

const int n = nums.size();

long long suffix = accumulate(begin(nums), end(nums), 0LL);

long long prefix = 0;

int best = INT_MAX;

int ans = 0;

for (int i = 0; i < n; ++i) {

prefix += nums[i];

suffix -= nums[i];

int cur = abs(prefix / (i + 1) - (i == n - 1 ? 0 : suffix / (n - i - 1)));

if (cur < best) {

best = cur;

ans = i;

}

return ans;

}

};

花花酱 LeetCode 2100. Find Good Days to Rob the Bank

By zxi on December 12, 2021

You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the i^th day. The days are numbered starting from 0. You are also given an integer time.

The i^th day is a good day to rob the bank if:

There are at least time days before and after the i^th day,
The number of guards at the bank for the time days before i are non-increasing, and
The number of guards at the bank for the time days after i are non-decreasing.

More formally, this means day i is a good day to rob the bank if and only if security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

Return a list of all days (0-indexed) that are good days to rob the bank. The order that the days are returned in does not matter.

Example 1:

Input: security = [5,3,3,3,5,6,2], time = 2
Output: [2,3]
Explanation:
On day 2, we have security[0] >= security[1] >= security[2] <= security[3] <= security[4].
On day 3, we have security[1] >= security[2] >= security[3] <= security[4] <= security[5].
No other days satisfy this condition, so days 2 and 3 are the only good days to rob the bank.

Example 2:

Input: security = [1,1,1,1,1], time = 0
Output: [0,1,2,3,4]
Explanation:
Since time equals 0, every day is a good day to rob the bank, so return every day.

Example 3:

Input: security = [1,2,3,4,5,6], time = 2
Output: []
Explanation:
No day has 2 days before it that have a non-increasing number of guards.
Thus, no day is a good day to rob the bank, so return an empty list.

Example 4:

Input: security = [1], time = 5
Output: []
Explanation:
No day has 5 days before and after it.
Thus, no day is a good day to rob the bank, so return an empty list.

Constraints:

1 <= security.length <= 10⁵
0 <= security[i], time <= 10⁵

Solution: Pre-Processing

Pre-compute the non-increasing days at days[i] and the non-decreasing days at days[i] using prefix and suffix arrays.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> goodDaysToRobBank(vector<int>& security, int time) {

const int n = security.size();

vector<int> before(n);

vector<int> after(n);

for (int i = 1; i < n; ++i)

before[i] = security[i - 1] >= security[i] ? before[i - 1] + 1 : 0;

for (int i = n - 2; i >= 0; --i)

after[i] = security[i + 1] >= security[i] ? after[i + 1] + 1 : 0;

vector<int> ans;

for (int i = time; i + time < n; ++i)

if (before[i] >= time && after[i] >= time)

ans.push_back(i);

return ans;

}

};

KMP Algorithm SP19

By zxi on March 31, 2020

KMP Algorithm, KMP 字符串搜索算法

Time complexity: O(m+n)
Space complexity: O(m)

Implementation

C++

#include <iostream>

#include <vector>

using namespace std;

// Author: Huahua

namespace KMP {

vector<int> Build(const string& p) {

const int m = p.length();

vector<int> nxt{0, 0};

for (int i = 1, j = 0; i < m; ++i) {

while (j > 0 && p[i] != p[j])

j = nxt[j];

if (p[i] == p[j])

++j;

nxt.push_back(j);

}

return nxt;

}

vector<int> Match(const string& s, const string& p) {

vector<int> nxt(Build(p));

vector<int> ans;

const int n = s.length();

const int m = p.length();

for (int i = 0, j = 0; i < n; ++i) {

while (j > 0 && s[i] != p[j])

j = nxt[j];

if (s[i] == p[j])

++j;

if (j == m) {

ans.push_back(i - m + 1);

j = nxt[j];

}

return ans;

}

}; // namespace KMP

void CheckEQ(const vector<int>& actual, const vector<int>& expected) {

if (actual != expected) {

std::cout << "expected:";

for (int v : expected)

std::cout << " " << v;

std::cout << " actual:";

for (int v : actual)

std::cout << " " << v;

std::cout << std::endl;

} else {

std::cout << "PASS" << std::endl;

}

int main(int argc, char** argv) {

CheckEQ(KMP::Build("ABCDABD"), {0, 0, 0, 0, 0, 1, 2, 0});

CheckEQ(KMP::Build("AB"), {0, 0, 0});

CheckEQ(KMP::Build("A"), {0, 0});

CheckEQ(KMP::Build("AA"), {0, 0, 1});

CheckEQ(KMP::Build("AAA"), {0, 0, 1, 2});

CheckEQ(KMP::Build("AABA"), {0, 0, 1, 0, 1});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "ABCDABD"), {15});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "AB"), {0, 4, 8, 11, 15, 19});

CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "B"), {1, 5, 9, 12, 16, 20});

CheckEQ(KMP::Match("AAAAA", "A"), {0, 1, 2, 3, 4});

CheckEQ(KMP::Match("AAAAA", "AA"), {0, 1, 2, 3});

CheckEQ(KMP::Match("AAAAA", "AAA"), {0, 1, 2});

CheckEQ(KMP::Match("ABC", "ABC"), {0});

return 0;

}

Python3

#!/usr/bin/env python3

from typing import List

# Author: Huahua

def Build(p: str) -> List[int]:

m = len(p)

nxt = [0, 0]

j = 0

for i in range(1, m):

while j > 0 and p[i] != p[j]:

j = nxt[j]

if p[i] == p[j]:

j += 1

nxt.append(j)

return nxt

def Match(s: str, p: str) -> List[int]:

n, m = len(s), len(p)

nxt = Build(p)

ans = []

j = 0

for i in range(n):

while j > 0 and s[i] != p[j]:

j = nxt[j]

if s[i] == p[j]:

j += 1

if j == m:

ans.append(i - m + 1)

j = nxt[j]

return ans

def CheckEQ(actual, expected):

if actual != expected:

print('actual: %s, expected: %s' % (actual, expected))

else:

print('Pass')

if __name__ == "__main__":

CheckEQ(Build("ABCDABD"), [0, 0, 0, 0, 0, 1, 2, 0])

CheckEQ(Build("AB"), [0, 0, 0])

CheckEQ(Build("A"), [0, 0])

CheckEQ(Build("AA"), [0, 0, 1])

CheckEQ(Build("AAAA"), [0, 0, 1, 2, 3])

CheckEQ(Build("AABA"), [0, 0, 1, 0, 1])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "ABCDABD"), [15])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "AB"), [0, 4, 8, 11, 15, 19])

CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "B"), [1, 5, 9, 12, 16, 20])

CheckEQ(Match("AAAAA", "A"), [0, 1, 2, 3, 4])

CheckEQ(Match("AAAAA", "AA"), [0, 1, 2, 3])

CheckEQ(Match("AAAAA", "AAAA"), [0, 1])

CheckEQ(Match("AAAAA", "AAAAA"), [0])

CheckEQ(Match("AABAABA", "AABA"), [0, 3])

Applications

LeetCode 28. strStr()

C++

// Author: Huahua

class Solution {

public:

int strStr(string haystack, string needle) {

if (needle.empty()) return 0;

auto matches = KMP::Match(haystack, needle);

return matches.empty() ? -1 : matches[0];

}

};

LeetCode 459. Repeated Substring Pattern

C++

// Author: Huahua

class Solution {

public:

bool repeatedSubstringPattern(string str) {

const int n = str.length();

auto nxt = KMP::Build(str);

return nxt[n] && nxt[n] % (n - nxt[n]) == 0;

}

};

1392. Longest Happy Prefix

C++

// Author: Huahua

class Solution {

public:

string longestPrefix(const string& s) {

return s.substr(0, KMP::Build(s).back());

}

};

花花酱 LeetCode 1163. Last Substring in Lexicographical Order

By zxi on August 18, 2019

Given a string s, return the last substring of s in lexicographical order.

Example 1:

Input: "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:

Input: "leetcode"
Output: "tcode"

Note:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Key observation: The last substring must be a suffix of the original string, can’t a substring in the middle since we can always extend it.
e.g. leetcode -> tcode, can’t be “t”, “tc”, “tco”, “tcod”

Solution 1: Brute Force

Try all possible suffixes.
Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua, 452 ms, 12.8 MB

class Solution {

public:

string lastSubstring(string_view s) {

string_view ans;

for (int i = 0; i < s.length(); ++i)

if (s.substr(i) > ans) ans = s.substr(i);

return string(ans);

}

};

Solution 2: Keep max and compare with candidates

Find the first largest letter as a starting point, whenever there is a same letter, keep it as a candidate and compare with the current best. If the later is larger, take over the current best.

e.g. “acbacbc”

“c” > “a”, the first “c” becomes the best.
“c” = “c”, the second “c” becomes a candidate
starting compare best and candidate.
“cb” = “cb”
“cba” < “cbc”, cand_i is the new best.

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

C++

// Author: Huahua

class Solution {

public:

string lastSubstring(string s) {

int max_i = 0;

char max_c = 0;

int cand_i = 0;

int l = 0;

for (int i = 0; i < s.length(); ++i) {

if (s[i] > max_c) {

// Find a better starting point.

max_c = s[i];

max_i = i;

cand_i = -1;

l = 1;

} else if (cand_i != -1) {

// Has a candidate.

if (s[i] > s[max_i + l]) {

// The candidate is larger.

max_i = cand_i;

cand_i = -1;

} else if (s[i] == s[max_i + l]) {

// The candidate is the same as current best.

++l;

} else {

// The candidate is smaller, no longer needed.

cand_i = -1;

}

} else if (s[i] == max_c) {

// Find a new candidate, starting with length 1.

cand_i = i;

l = 1;

}

return s.substr(max_i);

}

};

花花酱 LeetCode 820. Short Encoding of Words

By zxi on April 24, 2018

Problem

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

Idea

Remove all the words that are suffix of other words.

Solution

Time complexity: O(n*l^2)

Space complexity: O(n*l)

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int minimumLengthEncoding(vector<string>& words) {

unordered_set<string> s(words.begin(), words.end());

for (const string& w : words) {

for (int i = w.length() - 1; i > 0; --i)

s.erase(w.substr(i));

}

int ans = 0;

for (const string& w : s)

ans += w.length() + 1;

return ans;

}

};