[Solved] Strong Password Checker II LeetCode Contest Problem

Strong Password Checker II: You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Example 1:

Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.

Example 2:

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful. 
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful. 
Thus, [2,0,2] is returned.

Constraints:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 105
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 1010

Solution:

Explanation:

Java HashSet is implemented on HashMap, which has an initial size of 16. The size will not increase since the load factor 4 / 16 < 0.75. Generally speaking, space O(16) = O(1).

If you really wanted to optimize space, which is not really needed here, you could call new HashSet<>(4, 1), here 4 and 1 are initial size and load factor respectively. 

Time and Space Complexity

Time: O(n), space: O(1), where n = password.length()

    public boolean strongPasswordCheckerII(String password) {
        Set<Character> seen = new HashSet<>();
        for (int i = 0; i < password.length(); ++i) {
            char c = password.charAt(i);
            if (i > 0 && c == password.charAt(i - 1)) {
                return false;
            }
            if (Character.isLowerCase(c)) {
                seen.add('l');
            }else if (Character.isUpperCase(c)) {
                seen.add('u');
            }else if (Character.isDigit(c)) {
                seen.add('d');
            }else if ("!@#$%^&*()-+".contains(c + "")) {
                seen.add('s');
            }
        }
        return password.length() >= 8 && seen.size() == 4;
    }

    def strongPasswordCheckerII(self, password: str) -> bool:
        seen = set()
        for i, c in enumerate(password):
            if i > 0 and c == password[i - 1]:
                return False
            if c in "!@#$%^&*()-+":
                seen.add('s')
            elif c.isupper():
                seen.add('u')
            elif c.islower():
                seen.add('l')
            elif c.isdigit():
                seen.add('d')             
        return  len(password) > 7 and len(seen) == 4

class Solution {
    typedef long long ll;
    typedef long double ld;
    typedef vector<ll> vi;
    typedef pair<ll, ll> pi;
#define endl '\n'
    static const ll mod = 1e9;
public:
    bool strongPasswordCheckerII(string& s) {
        if(s.length()<8)
            return false;
        string specChars = "!@#$%^&*()-+";
        ll sz = s.length();
        bool dig = false,
            up = false,
            low = false,
            spec = false;
        for (ll i = 0;i < sz;++i) {
            dig |= s[i] >= '0' && s[i] <= '9';
            up |= s[i] >= 'A' && s[i] <= 'Z';
            low |= s[i] >= 'a' && s[i] <= 'z';
            spec |= specChars.find(s[i]) != string::npos;
            if (i && s[i] == s[i - 1])
                return false;
        }
        return (up && low && dig && spec);
    }
};

Happy Learning – If you require any further information, feel free to contact me.