strings (DSA)
1. PALINDROME PROBLEM OF STRING
Solution
- Convert the string to lowercase.
- Remove all the special characters and spaces from the string.
- Initialize two pointers, one at the beginning and one at the end of the string.
- Compare the characters pointed by the two pointers. If they are equal, move the left pointer to the right and the right pointer to the left. If they are not equal, return 0.
- Repeat step 4 until the two pointers cross each other.
If the two pointers cross each other, the string is a palindrome, and we can return 1
code:
public class Solution {
public int isPalindrome(String A) {
// Convert the string to lowercase
A = A.toLowerCase();
// Remove all the special characters and spaces from the string
A = A.replaceAll("[^a-zA-Z0-9]", "");
// Initialize two pointers
int left = 0;
int right = A.length() - 1;
// Compare the characters pointed by the two pointers
while (left < right) {
if (A.charAt(left) != A.charAt(right)) {
return 0;
}
left++;
right--;
}
return 1;
}
}
2.Remove consecutive characters
public class Solution {
public String solve(String A, int B) {
StringBuilder sb = new StringBuilder();
int n = A.length();
int i = 0;
while (i < n) {
int j = i;
while (j < n && A.charAt(i) == A.charAt(j)) {
j++;
}
int len = j - i;
if (len != B) {
sb.append(A.substring(i, j));
}
i = j
return sb.toString();
}}
3.Serialize
To add(append) length and delimiter to the strings in the array list
public class Solution {
public String serialize(ArrayList<String> A) {
StringBuilder sb=new StringBuilder();
for (String str : A){
sb.append(str).append(str.length()).append('~');
}
return sb.toString();
}
}
4.String And Its Frequency
public class Solution {
public String solve(String A) {
Map<Character, Integer> freqMap = new LinkedHashMap<>();
for (char c : A.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
StringBuilder sb = new StringBuilder();
for (char c : freqMap.keySet()) {
sb.append(c);
sb.append(freqMap.get(c));
}
return sb.toString();
}
}
5.Self Permutation
the code written. by me:
public class Solution {
public int permuteStrings(String A, String B) {
int n=A.length();
int m=B.length();
int count=0;;
if(n!=m)
{
count=0;
}
else{
char[] chars1 = A.toCharArray();
char[] chars2 = B.toCharArray();
Arrays.sort(chars1);
Arrays.sort(chars2);
boolean result= Arrays.equals(chars1, chars2);
if(result==true){
count=1;
}
}
return count;
}
}
the code by references:
public class Solution {
public int permuteStrings(String A, String B) {
if (A.length() != B.length()) {
return 0;
}
int[] count = new int[26]; // assuming only lowercase English alphabets
// count frequency of characters in A
for (int i = 0; i < A.length(); i++) {
count[A.charAt(i) - 'a']++;
}
// subtract frequency of characters in B
for (int i = 0; i < B.length(); i++) {
count[B.charAt(i) - 'a']--;
}
// check if all counts are zero
for (int i = 0; i < 26; i++) {
if (count[i] != 0) {
return 0;
}
}
6.Longest Common Prefix
public class Solution {
public String longestCommonPrefix(String[] A) {
String prefix = A[0]; // initialize prefix to first string in the array, "abcd"
for (int i = 1; i < A.length; i++) {
while (A[i].indexOf(prefix) != 0) { // check if prefix is a prefix of A[i]
prefix = prefix.substring(0, prefix.length() - 1); // remove last character of prefix
if (prefix.isEmpty()) {
return ""; // if prefix becomes empty, return empty string
}
}
}
return prefix; // returns ""
}
}
7.Amazing Subarrays
public class Solution {
public int solve(String A) {
int count = 0; // variable to count the number of amazing substrings
int n = A.length(); // length of the input string
for (int i = 0; i < n; i++) { // loop over all characters in the input string
char c = A.charAt(i); // get the i-th character in the input string
// check if the i-th character is a vowel (a, e, i, o, u, A, E, I, O, U)
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') {
// if it is a vowel, add the number of substrings that start with this character to the count
// the number of substrings that start with the i-th character is (n - i)
count += (n - i);
}
}
// take the modulus of the count with 10003 and return the result
return count % 10003;
}
}
8.Convert to Palindrome
done by me:
public class Solution {
public int solve(String A) {
int n=A.length();
int count=0;
int flag=0;
int i=0;
int j=n-1;
while(i<j){
if(A.charAt(i)==A.charAt(j)){
i++;
j--;
}
else{
count++;
if(count>1){
flag=0;
}
else{
if (i + 1 < n && A.charAt(i + 1) == A.charAt(j)) {
i++;
} else if (j - 1 >= 0 && A.charAt(i) == A.charAt(j - 1)) {
j--;
flag=1;
}
else{
flag=0;
}
}
}
}
return flag;
}
}
correct code:
public class Solution {
public int solve(String A) {
int n = A.length();
int i = 0, j = n - 1;
// Traverse the string from both ends
while (i < j) {
// If characters at both ends are different
if (A.charAt(i) != A.charAt(j)) {
// Check if removing the character at i or j makes the string a palindrome
boolean case1 = isPalindrome(A, i + 1, j);
boolean case2 = isPalindrome(A, i, j - 1);
// If either of the cases makes the string a palindrome, return 1
if (case1 || case2) {
return 1;
} else {
// If neither case makes the string a palindrome, it is impossible to make it a palindrome by removing one character
return 0;
}
}
// If characters at both ends are the same, move towards the center of the string
i++;
j--;
}
// If the entire string is a palindrome, removing one character will still result in a palindrome
return 1;
}
// Helper method to check if a string is a palindrome
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
9.Minimum Appends for Palindrome!
public class Solution {
public int solve(String A) {
int n=A.length();
int count =0;
int i=0;
int j=n-1;
while(i<j){
if(A.charAt(i)==A.charAt(j)){
i++;
j--;
}
else{
count=i+1;
i++;
j=n-1;
}
}
return count;
}
}
10.Minimum Parantheses!
public class Solution {
public int solve(String A) {
// Create a stack to keep track of opening parentheses
Stack<Character> stack = new Stack<>();
// Initialize the count of parentheses to be added to zero
int count = 0;
// Iterate over each character in the string
for (char c : A.toCharArray()) {
if (c == '(') {
// If the character is an opening parenthesis, push it onto the stack
stack.push(c);
} else if (c == ')') {
// If the character is a closing parenthesis
if (!stack.isEmpty() && stack.peek() == '(') {
// If there is a matching opening parenthesis in the stack, pop it from the stack
stack.pop();
} else {
// If there is no matching opening parenthesis in the stack, increment the count of parentheses to be added
count++;
}
}
}
// After iterating over the string, add the remaining opening parentheses in the stack to the count
count += stack.size();
// Return the count of parentheses to be added
return count;
}
}
11.Integer To Roman
public class Solution {
public String intToRoman(int A) {
// Define a mapping of decimal numbers to Roman numerals
int[] decimalValues = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] romanNumerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
// Build the Roman numeral string by repeatedly subtracting the largest decimal value
StringBuilder sb = new StringBuilder();
for (int i = 0; i < decimalValues.length; i++) {
while (A >= decimalValues[i]) {
sb.append(romanNumerals[i]);
A -= decimalValues[i];
}
}
return sb.toString();
}
}
// When the while loop is executed for a particular element i in the decimalValues array, it checks if the input integer A is greater than or equal to the current element in the array (decimalValues[i]). If A is greater than or equal to the current decimal value, it appends the corresponding Roman numeral (romanNumerals[i]) to the output string sb and subtracts the decimal value from A.
In the case of the input integer 42 and the decimalValues array, the first element to satisfy the condition A >= decimalValues[i] is 40, corresponding to the Roman numeral XL. The loop executes for i = 7 (the index of 40 in the decimalValues array), and appends the corresponding Roman numeral XL to sb, and subtracts 40 from A. After this, A becomes 2, and the loop proceeds to the next element in the decimalValues array.
I hope this clears up any confusion, and I apologize for any confusion caused by my previous response.
12.Roman To Integer:
public class Solution {
public int romanToInt(String A) {
HashMap<Character, Integer> romanValues = new HashMap<Character, Integer>();
romanValues.put('I', 1);
romanValues.put('V', 5);
romanValues.put('X', 10);
romanValues.put('L', 50);
romanValues.put('C', 100);
romanValues.put('D', 500);
romanValues.put('M', 1000);
int result = 0;
int prevValue = 0;
for (int i = 0; i < A.length(); i++) {
char currChar = A.charAt(i);
int currValue = romanValues.get(currChar);
result += currValue;
if (currValue > prevValue) {
result -= 2 * prevValue;
}
prevValue = currValue;
}
return result;
}
}
13.Add Binary Strings:
public class Solution {
public String addBinary(String A, String B) {
int n = A.length();
int m = B.length();
int i = n - 1;
int j = m - 1;
int carry = 0;
StringBuilder res = new StringBuilder();
while (i >= 0 || j >= 0) {
int sum = carry;
if (i >= 0) {
sum += A.charAt(i) - '0';
i--;
}
if (j >= 0) {
sum += B.charAt(j) - '0';
j--;
}
carry = sum / 2;
res.append(sum % 2);
}
if (carry > 0) {
res.append(carry);
}
return res.reverse().toString();
}
}
14.Length of Last Word
code by me:
public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
public int lengthOfLastWord(final String A) {
String[] arr=A.split(" ");
int n=arr.length;
String i=arr[n-1];
int len=i.length();
return len;
}
}
another code:
public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
public int lengthOfLastWord(final String A) {
int len = 0;
boolean foundWord = false;
for (int i = A.length() - 1; i >= 0; i--) {
char c = A.charAt(i);
if (c == ' ') {
if (foundWord) {
break;
}
} else {
foundWord = true;
len++;
}
}
return len;
}
}
public class Solution {
ReplyDeletepublic int solve(String A) {
int vowels = 0;
int consonant = 0;
int n = A.length();
for(int i = 0; i<n; i++){
if(isVowel(A.charAt(i))){
vowels++;
}
else{
consonant++;
}
}
return (vowels*consonant)%(1000000007);
}
public boolean isVowel(char c){
if(c== 'a' || c== 'e' || c== 'i' || c== 'o' || c== 'u'){
return true;
}
return false;
}
}
vowels and consonants ka code