Problem: A password is considered strong if the below conditions are all met:
- It has at least 6 characters and at most 20 characters.
- It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
- It does not contain three repeating characters in a row (i.e., "...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).
Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.
In one step, you can:
- Insert one character to password,
- Delete one character from password, or
- Replace one character of password with another character.
Example:
Input: password = "a" Output: 5 Explanation: We can insert any 5 characters including at least one uppercase character and at least one digit. We also need to make sure that there are no three repeating characters.
Approach: This problem is very hard to solve. Please have pen and paper with you to run through examples wherever you don't understand the approach. Let's start with the most basic approach to solve this question which is recursive approach and it is the easiest solution to understand. Let's go in depth of this basic solution:
For a recursive solution, First we need to define the method:
int GetMinSteps(int currIndex, int numOfChartecters, bool hasLowerCase, bool hasUpperCase, bool hasDigit, char lastCharacter, char secondLastCharacter)
- currIndex: The character of password at index which we are processing
- numOfChartecters: Number of characters we have added into the password till now
- hasLowerCase: Did we get any lowercase character in password[0...currIndex - 1]
- hasUpperCase: Did we get any uppercase character in password[0...currIndex - 1]
- hasDigit: Did we get any digit in password[0...currIndex - 1]
- lastCharacter: Last character processed
- secondLastCharacter: Second last character processed.
- Both lastCharacter and secondLastCharacter are need to check if there is any three repeating characters are there in the password.
- Return value: Minimum steps required to make a given password a valid password.
Okay. So now we have defined our method, we need to define the base condition here. If you see there are two base conditions
- numOfChartecters > 20, number of characters added in the password is more than 20. We need to return from here as we don't want to add more character.
- currIndex == length of password: Reached the end of string, nothing to process any more.
Let's see what we want to return in these base conditions:
If ( numOfChartecters > 20) // Invalid password, return some large value
return int.Max;
if (currIndex == n)
{
if (numOfChartecters < 6 || !hasLowerCase || !hasUpperCase || !hasDigit) // Invalid password
{
return int.Max;
}
// Valid password, no changes required
return 0;
}
So now we are done with our base condition, we can move to our operations:
Let's say minSteps = int.Max;
1. We just add the current character to password if it is not same as last character and second last character. Right!
IF NOT( password[currIndex] == lastCharacter AND password[currIndex] == secondLastCharacter)
minSteps = Min(minSteps,
GetMinSteps(
currIndex + 1, // Next index
numOfChartecters + 1, // 1 more character is added
hasLowerCase || IsLower(password[currIndex]), // setting lower case
hasUpperCase || IsUpper(password[currIndex]), // setting upper case
hasDigit || IsDigit(password[currIndex]), // setting digit
password[currIndex], // current character becomes last character
lastCharacter)) // last character becomes second last character
2. Insert a lowercase character:
minSteps = Min(minSteps,
GetMinSteps(
currIndex, // Added a character, index remains same
numOfChartecters + 1, // 1 more character is added
True), // added a lower case
hasUpperCase, // no change here
hasDigit, // no change
lastCharacter == 'z' ? 'x' : 'z', // add any char, newly added char becomes last char
lastCharacter) + 1) // last character becomes second last character, adding one as we made one change
3. Insert a uppercase character:
minSteps = Min(minSteps,
GetMinSteps(
currIndex, // Added a character, index remains same
numOfChartecters + 1, // 1 more character is added
hasLowerCase, // no change here
True, // added a upper case
hasDigit, // no change
lastCharacter == 'Z' ? 'X' : 'X', // add any char, newly added char becomes last char
lastCharacter) + 1) // last character becomes second last character, adding one as we made one change
4. Insert a digit:
minSteps = Min(minSteps,
GetMinSteps(
currIndex, // Added a character, index remains same
numOfChartecters + 1, // 1 more character is added
hasLowerCase, // no change here
hasUpperCase , // no change here
True, // added a digit
lastCharacter == '9' ? '8' : '9', // add any digit, newly added char becomes last char
lastCharacter) + 1) // last character becomes second last character, adding one as we made one change
5. Delete current character:
minSteps = Min(minSteps,
GetMinSteps(
currIndex + 1, // Remove a character, go to next index
numOfChartecters , // no character has been added
hasLowerCase, // no change here
hasUpperCase , // no change here
hasDigit, // no change here
lastCharacter, // Remains same
secondLastCharacter) + 1) // Second last character remains same, adding one as we made one change
6. Change to a lowercase character:
minSteps = Min(minSteps,
GetMinSteps(
currIndex + 1, // Changed a character, move to next
numOfChartecters + 1, // 1 more character is added
True), // changed to a lower case
hasUpperCase, // no change here
hasDigit, // no change
lastCharacter == 'z' ? 'x' : 'z', // change to any char, newly changed char becomes last char
lastCharacter) + 1) // last character becomes second last character, adding one as we made one change
7. Change to a uppercase character:
minSteps = Min(minSteps,
GetMinSteps(
currIndex + 1, // Changed a character, move to next index
numOfChartecters + 1, // 1 more character is added
hasLowerCase, // no change here
True, // changed to a upper case
hasDigit, // no change
lastCharacter == 'Z' ? 'X' : 'X', // changed to any char, newly changed char becomes last char
lastCharacter) + 1) // last character becomes second last character, adding one as we made one change
8. Change to a digit:
minSteps = Min(minSteps,
GetMinSteps(
currIndex, // change a character, move to next index
numOfChartecters + 1, // 1 more character is added
hasLowerCase, // no change here
hasUpperCase , // no change here
True, // added a digit
lastCharacter == '9' ? '8' : '9', // add any digit, newly added char becomes last char
lastCharacter) + 1) // last character becomes second last character, adding one as we made one change
Implementation in C#:
DP solution:
public static int StrongPasswordCheckerDP(string password)
{
if (password?.Length == 0)
{
return 6;
}
Dictionary<string, long> dp = new Dictionary<string, long>();
return (int)GetMinSteps(password, 0, 0, false, false, false, Char.MinValue, Char.MinValue, dp);
}
private static long GetMinSteps(
string password,
int currIndex,
int numCharacters,
bool hasLowerCase,
bool hasUpperCase,
bool hasDigit,
char lastCharacter,
char secondLastCharacter,
Dictionary<string, long> dp)
{
string key = $"{currIndex}-{numCharacters}-{hasLowerCase}-{hasUpperCase}-{hasDigit}-{lastCharacter}-{secondLastCharacter}";
if (dp.ContainsKey(key))
{
return dp[key];
}
if (numCharacters > 20)
{
dp.Add(key, int.MaxValue);
return int.MaxValue;
}
if (currIndex == password.Length)
{
if (numCharacters < 6 || !hasLowerCase || !hasUpperCase || !hasDigit)
{
dp.Add(key, int.MaxValue);
return int.MaxValue;
}
dp.Add(key, 0);
return 0;
}
long minSteps = int.MaxValue;
// Add current character
if (!(password[currIndex] == lastCharacter && password[currIndex] == secondLastCharacter))
{
minSteps = Math.Min(
minSteps,
GetMinSteps(
password,
currIndex + 1,
numCharacters + 1,
hasLowerCase || char.IsLower(password[currIndex]),
hasUpperCase || char.IsUpper(password[currIndex]),
hasDigit || char.IsDigit(password[currIndex]),
password[currIndex],
lastCharacter,
dp));
}
// Insert a lower case character
minSteps = Math.Min(
minSteps,
GetMinSteps(
password,
currIndex,
numCharacters + 1,
true,
hasUpperCase,
hasDigit,
lastCharacter == 'z' ? 'x' : 'z',
lastCharacter,
dp) + 1);
// Insert a upper case character
minSteps = Math.Min(
minSteps,
GetMinSteps(
password,
currIndex,
numCharacters + 1,
hasLowerCase,
true,
hasDigit,
lastCharacter == 'Z' ? 'X' : 'Z',
lastCharacter,
dp) + 1);
// Insert a digit
minSteps = Math.Min(
minSteps,
GetMinSteps(
password,
currIndex,
numCharacters + 1,
hasLowerCase,
hasUpperCase,
true,
lastCharacter == '9' ? '2' : '9',
lastCharacter,
dp) + 1);
// delete this character
minSteps = Math.Min(
minSteps,
GetMinSteps(
password,
currIndex + 1,
numCharacters,
hasLowerCase,
hasUpperCase,
hasDigit,
lastCharacter,
secondLastCharacter,
dp) + 1);
// Change a lower case character
minSteps = Math.Min(
minSteps,
GetMinSteps(
password,
currIndex + 1,
numCharacters + 1,
true,
hasUpperCase,
hasDigit,
lastCharacter == 'z' ? 'x' : 'z',
lastCharacter,
dp) + 1);
// change a upper case character
minSteps = Math.Min(
minSteps,
GetMinSteps(
password,
currIndex + 1,
numCharacters + 1,
hasLowerCase,
true,
hasDigit,
lastCharacter == 'Z' ? 'X' : 'Z',
lastCharacter,
dp) + 1);
// Change a digit
minSteps = Math.Min(
minSteps,
GetMinSteps(
password,
currIndex + 1,
numCharacters + 1,
hasLowerCase,
hasUpperCase,
true,
lastCharacter == '9' ? '2' : '9',
lastCharacter,
dp) + 1);
dp.Add(key, minSteps);
return minSteps;
}
Greedy Solution:
public static int StrongPasswordChecker(string password)
{
if (password?.Length == 0)
{
return 6;
}
int numMissingLetterTypes = 3;
for (int i = 0; i < password.Length; ++i)
{
if (char.IsLower(password[i]))
{
--numMissingLetterTypes;
break;
}
}
for (int i = 0; i < password.Length; ++i)
{
if (char.IsUpper(password[i]))
{
--numMissingLetterTypes;
break;
}
}
for (int i = 0; i < password.Length; ++i)
{
if (char.IsDigit(password[i]))
{
--numMissingLetterTypes;
break;
}
}
int numChangesReqd = 0;
int numRemoveOneCharReqd = 0;
int numRemoveTwoCharsReqd = 0;
int index = 2;
int currLengthOfRepeatingChars;
while (index < password.Length)
{
if (password[index] == password[index - 1] && password[index] == password[index - 2])
{
currLengthOfRepeatingChars = 2;
while (index < password.Length && password[index] == password[index - 1])
{
++index;
++currLengthOfRepeatingChars;
}
numChangesReqd += currLengthOfRepeatingChars / 3;
numRemoveOneCharReqd = currLengthOfRepeatingChars % 3 == 0 ? numRemoveOneCharReqd + 1 : numRemoveOneCharReqd;
numRemoveTwoCharsReqd = currLengthOfRepeatingChars % 3 == 1 ? numRemoveTwoCharsReqd + 1 : numRemoveTwoCharsReqd;
}
else
{
++index;
}
}
if (password.Length < 6)
{
return Math.Max(numMissingLetterTypes, 6 - password.Length);
}
else if (password.Length <= 20)
{
return Math.Max(numMissingLetterTypes, numChangesReqd);
}
else
{
int numOfDeletes = password.Length - 20;
numChangesReqd -= Math.Min(numOfDeletes, numRemoveOneCharReqd);
numChangesReqd -= Math.Min(Math.Max(numOfDeletes - numRemoveOneCharReqd, 0), 2 * numRemoveTwoCharsReqd) / 2;
numChangesReqd -= Math.Max(numOfDeletes - numRemoveOneCharReqd - numRemoveTwoCharsReqd * 2, 0) / 3;
return numOfDeletes + Math.Max(numChangesReqd, numMissingLetterTypes);
}
}
Complexity: O(n) for greedy solution
No comments:
Post a Comment