leetcode 420. strong password checker

Leet Code 420 Strong Password Checker (HARD)

by

LeetCode 420 Strong Password Checker : C++ / Java / C# / C /Python

C++ Solution

// C++ Solution Code Here
class Solution {
public:
    int strongPasswordChecker(string s) {
        bitset<3> requirements{111}; 
        list<int> repeats;
        auto it = s.begin();
        auto it2 = s.end();
        while (it != s.end()) {
            if (*it != *it2) {
                if (requirements.test(0) && islower(*it))
                    requirements.reset(0);
                if (requirements.test(1) && isupper(*it))
                    requirements.reset(1);
                if (requirements.test(2) && isdigit(*it))
                    requirements.reset(2);
            } else {
                while (it != s.end() && *it == *it2)
                    ++it;
                if (distance(it2, it) != 2)
                    repeats.push_back(distance(it2, it));
                if (it != s.end())
                    continue;
                else
                    break;
            }
            it2 = it;
            ++it;
        }
        repeats.sort([](const int &lhs, const int &rhs) { return (lhs % 3) < (rhs % 3); });
        int ans{0}, len{static_cast<int>(s.size())};
        while (len > 20) {
            if (!repeats.empty()) {
                if (repeats.front() == 3) {
                    repeats.pop_front();
                }
                else {
                    --repeats.front();
                    repeats.sort([](const int &lhs, const int &rhs) { return (lhs % 3) < (rhs % 3); });
                }
                ++ans;
                --len;
            }
            else {
                ans += len - 20;
                len = 20;
            }
        }
        int rep_ins{0};
        while (!repeats.empty()) {
            rep_ins += repeats.front() / 3;
            repeats.pop_front();
        }
        if ((len + rep_ins) < 6) {
            rep_ins += 6 - len - rep_ins;
        }
        ans += max(static_cast<int>(requirements.count()), rep_ins);
        return ans;
    }
};

Code Explanation :

Certainly! This C++ code is like a helper for making a strong password from a given text. A strong password is one that’s hard to guess, and it should follow some rules:

  1. It needs to have at least one small letter (like ‘a’).
  2. It needs to have at least one capital letter (like ‘A’).
  3. It needs to have at least one number (like ‘1’).
  4. It shouldn’t have the same character repeated three times in a row (like “aaa”).
  5. It should be at least 6 characters long but not more than 20 characters.

This code helps you find out how many changes you need to make to a given text to meet these rules. Here’s how it works:

  1. It uses a little checklist (called requirements) to keep track of whether you have met the first three rules. At the start, all three rules are not met (like a checkbox that is not ticked).
  2. It also keeps a list of how many times the same characters appear together in the text (for rule 4).
  3. Then, it looks at each letter in the text:
  • If the letter is different from the previous one, it checks if you have met the first three rules (small letter, capital letter, and number). If not, it checks them off.
  • If the letter is the same as the previous one, it counts how many times this letter repeats together until it’s different. This helps with rule 4.
  1. After checking the whole text, it sorts the list of repeated characters based on how many times they repeat (rule 4).
  2. Next, it starts making changes to the text:
  • If the text is longer than 20 characters, it tries to fix the problem of having the same character repeated three times in a row by removing one of them.
  • If there are no characters repeated three times in a row, it just removes one character from the list of repeated characters.
  • It keeps doing this until the text is 20 characters or less.
  1. It also calculates how many characters you need to add to the text to make it at least 6 characters long if it’s shorter.
  2. Finally, it adds up all the changes you made to meet the rules and gives you the total number. This total number is the minimum number of changes needed to make your text a strong password.

So, in simple terms, this code helps you find out how to make your password strong by counting the changes you need to make to meet the rules.

JAVA solution

Java Solution

// Java Solution Code Here
class Solution {
    public int strongPasswordChecker(String s) {
        int res = 0, a = 1, A = 1, d = 1;
        char[] carr = s.toCharArray();
        int[] arr = new int[carr.length];
        for (int i = 0; i < arr.length;) {
            if (Character.isLowerCase(carr[i])) a = 0;
            if (Character.isUpperCase(carr[i])) A = 0;
            if (Character.isDigit(carr[i])) d = 0;
            int j = i;
            while (i < carr.length && carr[i] == carr[j]) i++;
            arr[j] = i - j;
        }

        int total_missing = (a + A + d);
        if (arr.length < 6) {
            res += total_missing + Math.max(0, 6 - (arr.length + total_missing));
        } else {
            int over_len = Math.max(arr.length - 20, 0), left_over = 0;
            res += over_len;
            for (int k = 1; k < 3; k++) {
                for (int i = 0; i < arr.length && over_len > 0; i++) {
                    if (arr[i] < 3 || arr[i] % 3 != (k - 1)) continue;
                    arr[i] -= Math.min(over_len, k);
                    over_len -= k;
                }
            }
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] >= 3 && over_len > 0) {
                    int need = arr[i] - 2;
                    arr[i] -= over_len;
                    over_len -= need;
                }
                if (arr[i] >= 3) left_over += arr[i] / 3;
            }
            res += Math.max(total_missing, left_over);
        }
        return res;
    }
}

This Java code is an implementation of a solution to the LeetCode problem “Strong Password Checker.” The problem requires you to determine the minimum number of changes required to make a given password strong. A strong password has the following characteristics:

  1. It must contain at least one lowercase letter.
  2. It must contain at least one uppercase letter.
  3. It must contain at least one digit.
  4. It must not have three repeating characters in a row (e.g., “…aaa…” is not allowed).

Here’s a breakdown of how the code works:

  1. The code starts by initializing variables res, a, A, and d to 0. These variables are used to keep track of the number of required changes for lowercase letters, uppercase letters, and digits, respectively.
  2. It converts the input string s into a character array carr and creates an integer array arr of the same length as carr. arr is used to store the length of consecutive repeating characters in s.
  3. The code then iterates through the characters in s using a while loop and counts the number of lowercase letters (a), uppercase letters (A), and digits (d) in the string. It also calculates the lengths of consecutive repeating characters and stores them in the arr array.
  4. It calculates the total_missing variable, which represents the total number of missing character types (lowercase, uppercase, and digits) in the password.
  5. Depending on the length of the input password s, the code handles three cases:
  • If the length is less than 6 characters, it calculates the required changes to meet the minimum length of 6 characters and adds them to res.
  • If the length is greater than or equal to 6 characters, it calculates the required changes to satisfy the constraints of not having three repeating characters in a row and adds them to res.
  • It handles situations where there are excessive characters (length greater than 20) and adjusts res accordingly.
  1. Finally, the code returns the value of res, which represents the minimum number of changes needed to make the password strong.

This code is an efficient solution to the Strong Password Checker problem on LeetCode and uses dynamic programming to keep track of character repetitions and handle various cases based on the length of the input password. It’s a good example of solving a coding challenge with optimization in mind.

C# solution

C# Solution

// C# Solution Code Here
class Solution {
    public int StrongPasswordChecker(string s) {
        int charSum = GetRequiredChar(s);
        if (s.Length < 6) return Math.Max(charSum, 6 - s.Length);
            int replace = 0, ones = 0, twos = 0; 
            for (int i = 0; i < s.Length;) {
            int len = 1;
                while (i + len < s.Length && s[i + len] == s[i + len - 1]) len++;
                if (len >= 3) {
                    replace += len / 3;
                    if (len % 3 == 0) ones += 1;
                    if (len % 3 == 1) twos += 2;
                }
                i += len;
            }
            if (s.Length <= 20) return Math.Max(charSum, replace);
            int deleteCount = s.Length - 20;
            replace -= Math.Min(deleteCount, ones);
            replace -= Math.Min(Math.Max(deleteCount - ones, 0), twos) / 2;
            replace -= Math.Max(deleteCount - ones - twos, 0) / 3;
        return deleteCount + Math.Max(charSum, replace);
        }
        int GetRequiredChar(string s) {
            int lowerCase = 1, upperCase = 1, digit = 1;
            foreach (var c in s) {
                if (char.IsLower(c)) lowerCase = 0;
                else if (char.IsUpper(c)) upperCase = 0;
                else if (char.IsDigit(c)) digit = 0;
            }
            return lowerCase + upperCase + digit;
    }    
}

This C# code is a solution to the LeetCode problem “Strong Password Checker.” The goal of this problem is to determine the minimum number of changes required to make a given password strong. A strong password is defined as follows:

  1. It must contain at least 6 characters and at most 20 characters.
  2. It must contain at least one lowercase letter, one uppercase letter, and one digit.
  3. It cannot contain three repeating characters in a row (“…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met).

Here’s an explanation of the code:

  1. GetRequiredChar function:
  • This function is used to calculate the number of required character types (lowercase, uppercase, and digit) that are missing in the given string s.
  1. StrongPasswordChecker function:
  • It takes the input string s and calculates the minimum number of changes needed to make it a strong password.
  • charSum stores the count of missing character types (lowercase, uppercase, and digit).
  • If the length of the input string is less than 6, the code returns the maximum value between charSum and the difference between 6 and the length of s, indicating the number of characters that need to be added.
  • The code then iterates through the string to find sequences of repeating characters and calculates the number of replacements needed to break these sequences into groups of three (as repetitions of three or more characters can be reduced to just three).
  • Depending on the length of the repeating sequence, it increments replace, ones, and twos variables.
  • Next, it checks if the length of the string is greater than 20. If so, it calculates the number of characters that need to be deleted (deleteCount).
  • It then adjusts the replace count based on the deletion count, ensuring that replacements are used to break up repeating sequences to minimize changes.
  • Finally, it returns the sum of deleteCount and the maximum between charSum and replace, representing the minimum number of changes needed to make the password strong.

This code efficiently calculates the minimum number of changes required to meet the strong password criteria, taking into account the different conditions mentioned in the problem statement.

C solution

C Solution

// C Solution Code Here
int strongPasswordChecker(char * password){
    int length = strlen(password);
    int offences1 = 0;
    int offences2 = 0;
    int offences = 0;
    int r = 0;
    char prev = '\n';
    char curr;
    int repC = 1;
    int delrep[3] = {0};
    int maxrep = 0;
    for(int i = 0; i < length; i++) {
        curr = password[i];
        if(curr == prev) {
            repC++;
        } else {
            if(repC >= 3) {
                delrep[repC%3]++;
            }
            repC = 1;
            prev = curr;
        }
        if(repC % 3 == 0) {
            r++;
        }
        if(repC > 3 && repC % 3 == 1) {
            delrep[2]++;
        }
    }
    if(repC >= 3) {
        delrep[repC%3]++;
    }
    int v = 0;
    int vo = 0;
    int lc = 0;
    int uc = 0;
    int dc = 0;
    for(int i = 0; i < length; i++) {
        if(lc == 0 && islower(password[i]) != 0) {
            v++;
            lc = 1;
        }
        if(uc == 0 && isupper(password[i]) != 0) {
            v++;
            uc = 1;
        }
        if(dc == 0 && isdigit(password[i]) != 0) {
            v++;
            dc = 1;
        }
    }
    if(v < 3) {
        offences2 += 3 - v;
        vo += 3 - v;
        if(length == 5 && v == 1) {
            offences1++;
        }
    }
    if(length < 6 || length > 20) {
        int delete = length - 20;
        if(delrep[0] != 0) {
            delrep[0] = delrep[0] < delete ? delrep[0] : delete;
        }
        if(delrep[1] != 0) {
            delrep[1] = delrep[1] < (delete - delrep[0])/2 ? delrep[1] : (delete - delrep[0])/2;
        }
        if(delrep[2] != 0) {
            delrep[2] = delrep[2] < ((delete - delrep[0]) - delrep[1]*2)/3 ? delrep[2] : ((delete - delrep[0]) - delrep[1]*2)/3;
        }
        r-= delrep[0] + delrep[1] + delrep[2];
        int x = r > offences2 ?  r : offences2;
        return length < 6 ? 6 - length + offences1 : delete + x; 
    }    
    return vo < r ? r : vo;
}

This C code appears to be a solution for a problem related to strong password checking. The goal is to evaluate the strength of a given password based on certain criteria and make suggestions for improvements if the password is weak.

Here’s a simplified explanation of what this code does:

  1. It calculates the length of the input password using strlen(password) and initializes some variables to keep track of offenses, repetitions, and other information.
  2. It then iterates through each character of the password to check for repeating characters. If a character repeats three or more times consecutively, it increments the r variable and keeps track of how many such repetitions occur for later deletion.
  3. It also checks if the password contains at least one lowercase letter, one uppercase letter, and one digit. If any of these requirements are not met, it counts offenses (vo) and suggests necessary additions to meet the criteria.
  4. It checks the length of the password to see if it’s too short (less than 6 characters) or too long (more than 20 characters). If the password is too long, it calculates how many characters need to be deleted to meet the 20-character limit and adjusts the r variable accordingly.
  5. Finally, it returns the minimum number of changes needed to make the password strong, considering all the rules and conditions.

Here’s a quick summary of the variables used:

  • offences1: Counts offenses for passwords of length 5 with only one type of character.
  • offences2: Counts offenses for not having at least three types of characters (lowercase, uppercase, digit).
  • r: Counts the number of repeated characters.
  • prev and curr: Keep track of the previous and current characters during iteration.
  • repC: Counts the current repetition count.
  • delrep: An array to track how many repetitions of length 3 or more occur.
  • maxrep: Keeps track of the maximum number of repetitions.
  • v, lc, uc, dc: Flags for tracking lowercase, uppercase, and digit presence in the password.

This code aims to find the minimum number of changes (additions, deletions, or substitutions) required to make a password strong based on specific criteria. It does so by considering the length, repetitions, and character types in the input password.

Python solution

Python Solution

# Python Solution Code Here
class Solution(object):
    def strongPasswordChecker(self, s):
        missing_type = 3
        if any('a' <= c <= 'z' for c in s): missing_type -= 1
        if any('A' <= c <= 'Z' for c in s): missing_type -= 1
        if any(c.isdigit() for c in s): missing_type -= 1
        change = 0
        one = two = 0
        p = 2
        while p < len(s):
            if s[p] == s[p-1] == s[p-2]:
                length = 2
                while p < len(s) and s[p] == s[p-1]:
                    length += 1
                    p += 1                    
                change += length / 3
                if length % 3 == 0: one += 1
                elif length % 3 == 1: two += 1
            else:
                p += 1        
        if len(s) < 6:
            return max(missing_type, 6 - len(s))
        elif len(s) <= 20:
            return max(missing_type, change)
        else:
            delete = len(s) - 20
            change -= min(delete, one)
            change -= min(max(delete - one, 0), two * 2) / 2
            change -= max(delete - one - 2 * two, 0) / 3
            return delete + max(missing_type, change)

This Python code appears to be a solution for the LeetCode problem called “Strong Password Checker.” The problem requires you to determine the minimum number of changes required to make a given string a strong password, given certain rules and requirements.

Let’s break down the code step by step:

  1. The strongPasswordChecker function takes a string s as input and calculates the minimum number of changes needed to make it a strong password.
  2. It initializes the variable missing_type to 3, which represents the types of characters that are missing in the password (lowercase letters, uppercase letters, and digits).
  3. The code then checks if the string contains at least one lowercase letter, one uppercase letter, and one digit. If any of these types is missing, it decreases the missing_type variable accordingly.
  4. It initializes some variables (change, one, and two) to keep track of changes needed to satisfy the requirements of a strong password.
  5. It iterates through the string using a while loop, comparing each character with the two previous characters. If it finds three consecutive characters that are the same, it calculates how many characters need to be changed to satisfy the requirement that at most two consecutive characters of the same type are allowed in a strong password. It updates the change, one, and two variables accordingly.
  6. If the length of the string is less than 6 characters, it returns the maximum value between missing_type and 6 - len(s). This is because the minimum length of a strong password is 6 characters.
  7. If the length of the string is between 6 and 20 characters (inclusive), it returns the maximum value between missing_type and change. This is because you want to minimize the changes while ensuring the password is strong.
  8. If the length of the string is greater than 20 characters, it calculates the number of characters that need to be deleted (more than 20 characters). It then adjusts the change variable based on the number of deletions required while considering the constraints on consecutive characters. Finally, it returns the sum of the number of characters to delete and the maximum value between missing_type and change.

This code is a concise and efficient solution to the “Strong Password Checker” problem, taking into account the constraints and requirements specified in the problem statement. It effectively calculates the minimum number of changes required to make a given string a strong password.

About Nilesh Raut

I am Nilesh,3+ years Exp of SEO, content writing, and keyword research. Also rocks it as a software dev with skills in OS, web dev, Flask, Python, C++, data structures, and algorithms. 3 on Leetcode, 5*on Hackerrank more platform.

View all posts by Nilesh Raut | Website

Leave a Reply